\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{vmumath}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{avo_book}
\usepackage{subcaption}
\usepackage[a4paper,left=15mm,right=15mm,top=30mm,bottom=20mm]{geometry}
\parindent=0mm
\parskip=3mm
\noaftermath
\pagestyle{empty}


\begin{document}




\begin{center}
\LARGE Перечисление непомеченных объектов.
\end{center}

\section{Понятие непомеченного объекта}

\myitem В предыдущей главе мы с помощью основных операций над экспоненциальными производящими функциями научились перечислять большое количество помеченных объектов, таких, например, как связные графы, эйлеровы графы, двудольные графы, деревья, и так далее. Однако при более тщательном анализе полученных результатов практически у любого читателя, впервые сталкивающегося с задачами перечисления графов, возникает довольно естественный вопрос --- а зачем нам различать графы, отличающиеся друг от друга лишь пометками своих вершин? 


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/labelled_conn.eps}
\caption{Помеченные связные графы на трех вершинах}
\label{fig:labelled_conn}
\end{figure}


\mysubitem Рассмотрим, к примеру, связные простые графы, построенные на $n$ различимых вершинах. На рис.\ref{fig:labelled_conn} показаны все такие графы, отвечающие случаю $n=3$. Понятно, что последние три из них отличаются лишь разметкой своих вершин и представляют собой, по сути, одно и то же дерево. Иными словами, более логичным и естественным было бы утверждение о том, что на трех вершинах можно построить всего лишь два существенно различающихся между собой связных графа --- изображенный на рис.\ref{fig:unlabelled_conn},a циклический граф, а также дерево, показанное на рис.\ref{fig:unlabelled_conn},b. Такие графы, в отличие от помеченных графов, представленных на рис.\ref{fig:labelled_conn}, естественно называть \emph{непомеченными} графами. 


\begin{figure}[h]
\centering
\begin{tabular}[t]{c}
	\begin{subfigure}[b]{0.4\textwidth}
	\centering
    		\includegraphics[scale=0.6]{pics/unlabelled_conn.eps}
 	\caption{}
	\end{subfigure}
	\begin{subfigure}[b]{0.4\textwidth}
	\centering
    		\includegraphics[scale=0.6]{pics/unlabelled_conn2.eps}
 	\caption{}
	\end{subfigure}
\end{tabular}
\caption{Непомеченные связные графы}
\label{fig:unlabelled_conn}
\end{figure}

На этом месте мы, однако, сталкиваемся с довольно-таки неочевидной проблемой --- а как же нам формально определить, что есть такое непомеченный граф? Оказывается, наиболее естественный способ дать такое определение связан с понятием внутренней симметрии перечисляемых объектов.


\mysubitem В качестве характерного примера обратимся к задаче о подсчете количества триангуляций правильных $(n+2)$-угольников. Еще в первой главе мы выяснили, что количество таких триангуляций в случае, когда вершины многоугольника помечены цифрами от $1$ до $(n+2)$, расположенными в циклическом порядке против часовой стрелки, описывается числами Каталана $c_n$. Так, для $n=2$ имеются две различные триангуляции квадрата с помеченными вершинами, для $n=3$ --- пять, а для $n=4$ --- четырнадцать (рис.\ref{fig:triang}). 

\begin{figure}[h]
\centering
\begin{tabular}[t]{c}
	\begin{subfigure}[b]{0.28\textwidth}
	\centering
    		\includegraphics[scale=0.6]{pics/triang_2.eps}
 	\caption{}
	\end{subfigure}
	\begin{subfigure}[b]{0.7\textwidth}
	\centering
    		\includegraphics[scale=0.6]{pics/triang_3.eps}
 	\caption{}
	\end{subfigure}
	
\\
\\
	\begin{subfigure}[b]{0.98\textwidth}
	\centering
    		\includegraphics[scale=0.6]{pics/triang_4.eps}
 	\caption{}
	\end{subfigure}
\end{tabular}
\caption{Триангуляции}
\label{fig:triang}
\end{figure}



Однако интуитивно ясно, что различать две триангуляции квадрата и пять триангуляций пятиугольника, показанные на рис.\ref{fig:triang},a и рис.\ref{fig:triang},b, в общем-то, не следует --- все они переходят друг в друга при поворотах этих фигур на $90^{\circ}$ градусов и $72^{\circ}$ градуса соответственно. 

Чуть более сложная ситуация имеется у нас с перечислением триангуляций правильных шестиугольников (рис.\ref{fig:triang},c). Шесть первых триангуляций, показанных на рис.\ref{fig:triang},c, отличаются друг от друга лишь тем, в какой из шести вершин сходятся образующие эти триангуляции треугольники, так что мы их можем не различать. Не различать мы можем и две следующие триангуляции, которые переходят друг в друга при поворотах на $60^{\circ}$. Наконец, шесть оставшихся триангуляций можно разбить на два класса по три триангуляции, переходящие друг в друга при поворотах на $120^{\circ}$. Иными словами, с точностью до поворотов вокруг центра симметрии правильного шестиугольника у нас существует всего четыре принципиально отличающихся друг от друга триангуляции этой фигуры, изображенные на рис. \ref{fig:unlabelled_6}.

\begin{figure}[h]
\centering
  		\includegraphics[scale=0.6]{pics/triang_different.eps}
\caption{Триангуляции непомеченного шестиугольника}
\label{fig:unlabelled_6}
\end{figure}

Теперь можно заметить, что и это количество мы можем уменьшить. Действительно, две последние триангуляции переходят друг в друга при отражении вокруг любой из шести осей симметрии правильного шестиугольника. С формальной точки зрения это означает, что с точностью до поворотов и отражений у нас остается всего лишь три принципиально различные триангуляции правильного шестиугольника.

\mysubitem Пример с триангуляциями правильного $(n+2)$-угольника показывает нам, что любой непомеченный объект представляет собой, по сути, некоторое подмножество помеченных объектов, переходящих в себя под действием той или иной группы симметрии этих объектов. При этом количество объектов в каждом подмножестве, а следовательно, и количество таких подмножеств, существенным образом зависит от того, какую именно группу симметрии мы рассматриваем.

Так, если мы возьмем в качестве группы симметрии правильного шестиугольника группу $C_6$ вращений этого шестиугольника относительно центра его симметрии, то мы получим четыре различных триангуляции. Если же мы в качестве такой группы выберем полную группу $D_6$ симметрий правильного шестиугольника, то у нас останется всего лишь три различные триангуляции. 

\myitem Итак, подводя итоги, мы можем сказать, что любой непомеченный объект представляет собой некоторый класс эквивалентности на множестве $X$ всех помеченных объектов данного типа. При этом само отношение эквивалентности на этом множестве задается действием группы $G$ на $X$ --- как правило, той или иной группы симметрий рассматриваемого нами объекта. Все, что нам осталось --- это дать строгое формальное определение действия группы $G$ на множестве $X$.

\mysubitem Напомним вначале определение самой группы $G$.

\begin{defin}
Группой $G$ называется множество с введенной на ней бинарной операцией $'\cdot'$, удовлетворяющей следующим трем аксиомам (аксиомам группы):
\begin{enumerate}
\item Ассоциативность операции $'\cdot'$: для любых трех элементов $f,g,h\in G$ 
$$
f\cdot(g\cdot h)=(f\cdot g)\cdot h.
$$
\item Наличие нейтрального элемента $e\in G$, то есть такого элемента группы, для которого 
$$
g\cdot e=e\cdot g=g \qquad \text{для любого}\quad g\in G.
$$
\item Наличие обратного элемента: для любого $g\in G$ существует элемент $g^{-1}\in G$, такой, что
$$
g^{-1}\cdot g=g\cdot g^{-1}=e.
$$
\end{enumerate}
\end{defin}

\mysubitem Рассмотрим теперь некоторое множество $X$ --- например, множество всех помеченных простых связных графов, построенных на $n$ вершинах, множество всех помеченных триангуляций правильного $(n+2)$-угольника, и так далее. Пусть у нас также имеется некоторая группа $G$ с бинарной операцией $\cdot$, например, циклическая группа $C_{n+2}$ вращений правильного $(n+2)$-угольника. 

\begin{defin} (Левым) действием группы $G$ на множестве $X$ называется бинарный оператор
$$
\circ:\qquad G\times X\,\,\longrightarrow\,\,X,
$$
удовлетворяющий следующим двум аксиомам:

\begin{enumerate}
\item Ассоциативность:
$$
(g\cdot h)\circ x=g\circ (h\circ x)\qquad \forall\, g,h\in G,\quad x\in X.
$$

\item Тождественность:
$$
e\circ x=x\qquad \forall\, x\in X,
$$
где $e$ --- нейтральный элемент группы $G$.
\end{enumerate}
\end{defin}

\begin{rem} \label{est_gom} Из определения действия группы $G$ на множестве $X$ следует, что при любом фиксированном $g\in G$ оператор $\circ$ задает биективное отображение $\circ_g:\,X\to X$ множества $X$ в себя, сопоставляющее любому $x\in X$ единственный элемент $y\in X$, равный $y=g\circ x$. Биективность этого отображения следует хотя бы из того, что для любого такого отображения, задаваемого $g\in G$, существует единственное обратное ему отображение, задаваемое обратным к $g$ в группе $G$ элементом $g^{-1}$ и сопоставляющее любому $y\in X$ элемент $g^{-1}\circ y=x$. 

Любое же биективное отображение конечного множества в себя можно трактовать как некоторую перестановку $\sigma_g$ множества $X$, т.е. как некоторый элемент симметрической группы $S_{n}$, $n=|X|$, всех перестановок этого $n$-элементного множества $X$. Поэтому любое действие группы $G$ на множестве $X$ задает нам некоторый гомоморфизм группы $G$ в некоторую подгруппу $\Sigma_G$ симметрической группы $S_{n}$, $n=|X|$. Образ $\Sigma_G$ этого гомоморфизма часто называют \emph{группой перестановок} множества $X$.
\end{rem}



\mysubitem Рассмотрим некоторые характерные примеры действий группы $G$ на множестве $X$.

\begin{examp} Тривиальное действие: для любого $x\in X$ и любого $g\in G$
$$
g\circ x=x.
$$
Такое действие задает гомоморфизм группы $G$ в тривиальную подгруппу $\Sigma_G=\{\id\}$ симметрической группы $S_{n}$, $n=|X|$, состоящую из единственного элемента --- тождественной перестановки $\id$. Отсюда, в частности, следует, что различные элементы $g\in G$ в общем случае не обязаны соответствовать \emph{различным} перестановкам $\sigma_g$ множества $X$. Иными словами, в общем случае это действительно гомоморфизм, а не изоморфизм группы $G$ в группу $\Sigma_G$ перестановок множества $X$. Впрочем, это, скорее, исключение, чем правило --- обычно действие $G$ на $X$ вводят так, чтобы группы $G$ и $\Sigma_G$ были изоморфны друг другу.
\end{examp}

\begin{examp} Действия группы $G$ на самой себе:
$$
\begin{array}{llcl}
(1):& \qquad \mbox{левое действие:}&\qquad g\circ x=g\cdot x&
\quad \forall\,g\in G,\quad \forall\,x\in G; \\[2ex]
(2):& \qquad \mbox{действие сопряжением:}&\qquad g\circ x=g\cdot x \cdot g^{-1}  &
\quad \forall\,g\in G,\quad \forall\,x\in G.
\end{array}
$$
\end{examp}

\begin{examp} Если мы рассматриваем какой-то геометрический объект $\Gamma$, то в качестве $G$, как правило, выступает группа симметрий этого объекта, т.е. группа всех движений евклидова пространства, переводящих объект $\Gamma$ в себя. Например, группа симметрий правильного многогранника действует на множестве $X_v$ вершин, множестве $X_e$ ребер и множестве $X_f$ граней этого многогранника. 
\end{examp}


\mysubitem Оказывается, любое действие $G$ на $X$ порождает на этом множестве $X$ отношение эквивалентности следующим образом:
$$
x\sim y,\qquad \mbox{если} \quad \exists \,g\in G:\quad g\circ x=y.
$$

Проверим, что введенное таким образом отношение удовлетворяет всем необходимым аксиомам. 

\begin{enumerate}
\item \emph{Рефлексивность:} $x\sim x$ для любого $x\in X$, так как для любого $x\in X$ существует
$e\in G$ --- нейтральный элемент группы, такой, что $e\circ x=x$.

\item \emph{Симметричность:} если $x\sim y$, т.е. существует $g\in G$, такой, что $g\circ x=y$, то и
$y\sim x$, так как существует $h\in G$, $h=g^{-1}$, такой, что $h\circ y=x$.

\item \emph{Транзитивность:} если $x\sim y$, т.е. существует $g\in G: \,\,g\circ x=y$, и если $y\sim
z$, т.е. существует $h\in G: \,\,h\circ y=z$, то, очевидно, существует и элемент $h\cdot g\in
G:\,\,(h\cdot g)\circ x=z$, т.е. $x\sim z$. 
\end{enumerate}

Как следствие, множество $X$ с помощью этого отношения разбивается на попарно непересекающиеся подмножества --- классы эквивалентности, которые в случае действия $G$ на $X$ имеют специальное название --- они называются орбитами элементов множества $X$.

\begin{defin} Орбитой элемента $x\in X$ под действием группы $G$ называется подмножество
$$
Gx:=\{g\circ x\in X\,|\,g\in G\}\,\,\subseteq \,\,X
$$
всех образов этого элемента под действием группы $G$. Соответствующее фактор-множество, т.е. множество всех таких орбит $Gx$, обозначается обычно $X/G$.
\end{defin}

\mysubitem Теперь мы вновь можем вернуться к понятию непомеченного объекта. Пусть $X$ есть $n$-элементное множество помеченных объектов, а $G$ есть некоторая группа симметрии любого элемента этого множества. Действие группы $G$ на $X$ разбивает все множество помеченных объектов на классы эквивалентности --- орбиты элементов $x\in X$ под действием группы $G$. Любой такой класс эквивалентности мы и будем называть непомеченным объектом.


\myitem С точки зрения комбинаторики интерес представляет поиск числа орбит, т.е. нахождение мощности описанного выше фактор-множества $X/G$. В простейших случаях это делается довольно легко. 

\mysubitem Рассмотрим несколько примеров.

\begin{examp}[задача о хороводе] \label{examp:chorovod}
Шесть девушек водят хоровод. Сколько существует способов его организовать? 
\end{examp}

\decis Если бы девушки стояли неподвижно, то тогда существовало бы $6!$ различных способов расставить их по местам на окружности. Иными словами, в этом примере множество $X$ совпадает с множеством всех перестановок шести различных элементов.

Но девушки в хороводе ходят по кругу, поэтому расположение девушек относительно окружающих их предметов не существенно. Важно лишь их взаимное расположение друг относительно друга. Как следствие, любые начальные расположения девушек, переходящие в себя при вращениях, следует считать эквивалентными, т.е. не различать.

С формальной точки зрения это означает, что на множестве $X=S_6$ всех перестановок шести элементов действует циклическая группа $G=C_6$ --- группа вращений. Нас же интересует количество орбит элементов множества $X$ под действием группы $G$, т.е. мощность фактор-множества $X/G$.

Упрощающим фактом в данном примере является то, что количество элементов в любой орбите является одинаковым и равным порядку $|G|$ группы, т.е. шести. Действительно, любой начальной расстановке девушек в хороводе можно сопоставить некоторую перестановку шести различных чисел вида
$$
\left(\begin{array}{cccccc}
1&2&3&4&5&6\\[2ex]
i_1&i_2&i_3&i_4&i_5&i_6
\end{array}\right).
$$
В результате действия группы $G=C_6$ мы из любой такой перестановки получаем следующие шесть отличных друг от друга перестановок:
$$
\left(\begin{array}{cccccc}
1&2&3&4&5&6\\[2ex]
i_1&i_2&i_3&i_4&i_5&i_6
\end{array}\right)\neq \left(\begin{array}{cccccc}
1&2&3&4&5&6\\[2ex]
i_2&i_3&i_4&i_5&i_6&i_1
\end{array}\right) \neq \ldots\neq
\left(\begin{array}{cccccc}
1&2&3&4&5&6\\[2ex]
i_6&i_1&i_2&i_3&i_4&i_5
\end{array}\right).
$$
Поэтому порядок $|Gx|=6$ для любого элемента $x\in X$, и мы имеем следующую простую формулу для подсчета количества всех орбит:
$$
|X/G|=\dfrac{|X|}{|Gx|}=\dfrac{6!}{6}=5!=120.
$$ \qed

\mysubitem Иногда рассмотренную в примере \ref{examp:chorovod} задачу формулируют как задачу об ожерелье. Ожерельем называется украшение, состоящее из $n$ драгоценных камней и имеющее две стороны --- лицевую и изнаночную. В задаче требуется найти количество ожерелий, состоящих из шести различных драгоценных камней.

Наряду с этой задачей часто рассматривают и так называемую задачу о браслете. Браслет, как и ожерелье, состоит из $n$ камней, однако, в отличие от ожерелья, две его стороны --- лицевая и изнаночная --- никак не отличаются друг от друга.

\begin{examp}[задача о браслете] \label{examp:braslet}
Сколько существует различных браслетов, состоящих из шести камней шести различных цветов? 
\end{examp}

\decis Отличие данной задачи от задачи об ожерелье состоит в том, что браслет мы можем переворачивать, а ожерелье нет. Как следствие, в задаче о браслете на множестве $X=S_6$ действует группа $G=D_6$ симметрий правильного шестиугольника, $|G|=12$. Так как все остальные рассуждения предыдущего примера остаются в силе, то количество различных браслетов рассчитывается по формуле
$$
|X/G|=\dfrac{|X|}{|Gx|}=\dfrac{6!}{12}=60.
$$
\qed

\mysubitem Возьмем теперь два одинаковых кубика, как-то раскрасим грани каждого из них, положим кубики в мешок и в этом мешке их перемешаем. Если в результате этих операций мы не сможем отличить один кубик от другого, то говорят, что способы их раскраски геометрически одинаковы.

\begin{examp}[задача о раскраске граней куба] \label{examp:cube_6_colours}
Сколько существует геометрически различных способов раскраски шести граней куба в шесть различных цветов?  
\end{examp}

\decis Как и в двух предыдущих примерах, множеству $X$ раскраски шести граней кубика в шесть различных цветов можно взаимно-однозначно сопоставить множество $S_6$ всех перестановок шести элементов. Но теперь на этом множестве действует группа $G$ симметрий куба. Далее, как и в примерах \ref{examp:chorovod} и \ref{examp:braslet}, и ровно по тем же самым соображениям, количество элементов в любой орбите одинаково и равно порядку $|G|$ группы. Однако в данном случае легче даже сосчитать не порядок группы, а количество элементов в любой орбите.

Действительно, любую грань, окрашенную в один из шести цветов, можно либо оставить на месте, либо перевести в любую из оставшихся пяти граней. Всего имеем, таким образом, шесть различных вариантов. При этом для любого из этих вариантов существует четыре различных способа окраски граней, прилегающих к данной. Эти способы получаются друг из друга поворотами относительно оси, проходящей через центр выбранной грани и центр грани, ей противоположной. Итого количество элементов в орбите любого элемента $x$ равно $|Gx|=6\cdot 4=24$, и поэтому $|X/G|=6!/24=30$. \qed

\myitem Во всех разобранных выше примерах количество элементов $x\in X$, принадлежащих любой орбите $Gx$, было одинаково и равно порядку $|G|$ группы $G$. Однако это скорее исключение, чем правило: в большинстве содержательных перечислительных задач количество элементов в различных орбитах различно. 

\mysubitem Начнем со следующего простейшего примера.

\begin{examp} 
Найти количество геометрически различных способов раскраски вершин правильного треугольника в не более чем два цвета.
\end{examp}

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/triangle_color.eps}
\caption{Раскраски вершин треугольника}
\label{fig:triangle_color}
\end{figure}


\decis Перебрав вручную все варианты, несложно убедиться, что всего существует $4$ геометрически различные способы окраски вершин треугольника (рис.\ref{fig:triangle_color}). Проверим, получится ли это число с использованием описанного в примерах \ref{examp:chorovod}--\ref{examp:cube_6_colours} подхода.

В рассматриваемом примере в качестве множества $X$ выступает множество правильных треугольников с помеченными и окрашенными вершинами. Любая из трех вершин может быть независимо от двух других вершин покрашена либо в черный, либо в белый цвет. Поэтому всего существует $2^3$ способов окраски этих вершин. Как следствие, мощность $|X|$ множества $X$ равна $8$. На этом множестве $X$ действует группа $D_3$ симметрий правильного треугольника, порядок которой равен шести. Видно, что $8$ на $6$ нацело не делится. Уже из этого обстоятельства следует, что подход, описанный в примерах \ref{examp:chorovod}--\ref{examp:cube_6_colours}, здесь не проходит.

Причина нашей неудачи как раз и заключается в том, что в рассматриваемой задаче количество элементов в разных орбитах различно и отличается от порядка группы $D_3$. Действительно, пусть элементу $x_1\in X$ соответствует треугольник, все помеченные вершины которого окрашены в белый цвет. Очевидно, что для такого элемента
$$
g\circ x_1=x_1 \qquad \qquad \forall\,g\in G.
$$
Как следствие, мощность орбиты этого элемента равна единице. Тот же результат справедлив и для элемента $x_8\in X$, отвечающего окраске всех трех вершин в черный цвет.

Оставшееся подмножество способов окраски вершин треугольника разбивается под действием группы $G$ на две орбиты, мощность каждой из которых равна трем. Действительно, пусть элементам $x_2$, $x_3$ и $x_4$ отвечают три способа окраски вершин треугольника в два цвета, при которых одна из трех вершин окрашена в белый, а две других --- в черный цвет. Несложно убедиться в том, что под действием различных элементов группы $G$ эти элементы переходят друг в друга. Тот же результат справедлив и для элементов $x_5$, $x_6$, $x_7$ множества $X$, отвечающих двум белым вершинам и одной черной.\qed

\mysubitem Вернемся к подсчету количества всех триангуляций правильных $(n+2)$-уголь\-ни\-ков. В этой задаче в качестве $X$ выступает множество всех возможных триангуляций правильных $(n+2)$-угольников с помеченными вершинами. На этом множестве может действовать либо группа $C_{n+2}$ вращений, либо группа $D_{n+2}$ симметрий правильного $(n+2)$-угольника. Задача состоит в подсчете количества $|X/G|$ орбит элементов множества $X$ под действием группы $G$, $G=C_{n+2}$ или $G=D_{n+2}$.  

Рассмотрим вначале триангуляции правильного пятиугольника $(n=3)$. Для таких триангуляций количество элементов в орбите как в случае действия группы $C_{n+2}=C_5$ вращений правильного пятиугольника, так и в случае действия полной группы $D_{n+2}=D_5$ симметрий правильного пятиугольника одинаково, равно $(n+2)=5$ и совпадает с количеством элементов в множестве $X$. Как следствие, количество триангуляций пятиугольника с непомеченными вершинами равно $5/5=1$. 

Однако уже в случае $n=4$ (триангуляции правильного шестиугольника) ситуация значительно сложнее. В этом случае под действием группы $C_{n+2}=C_6$ вращений все множество $X$ таких триангуляций разбивается на четыре орбиты, только в одной из которых количество элементов совпадает с порядком группы и равно шести. В двух других количество элементов равняется трем, а в последней это количество равно двум. Под действием полной группы $D_{n+2}=D_6$ симметрий правильного шестиугольника то же самое множество $X$ разбивается на три орбиты, количество элементов в которых равняется $|Gx_1|=|Gx_2|=6$, $|Gx_3|=2$. 

Дальнейшие рассуждения, приводящие к решению этой задачи при произвольном значении параметра $n$, можно посмотреть в упражнении \ref{en_plane_2_trees} к данному параграфу.


\mysubitem Итак, подводя предварительные итоги, мы можем сказать следующее. В простейшем случае, когда $|Gx|=|G|$ для любого $x\in X$, количество орбит рассчитать достаточно легко --- для этого достаточно количество $|X|$ элементов множества $X$ поделить на порядок $|G|$ группы $G$:
$$
|X/G|=\dfrac{|X|}{|G|}.
$$
В более же сложных случаях, когда количество элементов в разных орбитах различно,
$$
\dfrac{|X|}{|G|}<|X/G|\leq |X|.
$$
На примерах мы убедились, что в этом случае задача подсчета количества орбит становится значительно менее тривиальной. В следующем параграфе мы покажем, как можно упростить решение этой задачи.  


\section*{Упражнения}

\begin{exerc} Семь человек садятся за круглый стол. Считается, что способы рассадки этих людей совпадают, если при каждой такой рассадке любой человек имеет около себя одних и тех же соседей. Сколько возможных способов рассадки людей вокруг стола существует?
\end{exerc}

\begin{exerc} Подсчитать количество различных ожерелий, состоящих из пяти камней красного цвета и двух камней синего цвета.
\end{exerc}

\begin{exerc} Подсчитать количество различных браслетов, состоящих из семи камней красного цвета и трех камней синего цвета.
\end{exerc}


\begin{exerc} Подсчитать количество геометрически различных способов окраски вершин квадрата в не более чем два цвета.
\end{exerc}

\begin{exerc} \label{en_plane_2_trees}
Подсчитать количество различных триангуляций правильного $(n+2)$-угольника с непомеченными вершинами при условии, что на множестве таких триангулируемых многоугольников действует только группа вращений.
\end{exerc}


\section*{Решение упражнений}

\begin{sol_exerc}
По сути, данная задача полностью эквивалентна задаче о подсчете количества различных браслетов, сделанных из семи камней семи различных цветов. Действительно, и в том, и в другом случае на множестве $X$ перестановок семи элементов действует одна и та же группа $D_7$ симметрий правильного семиугольника. Мощность орбиты любого элемента одинакова и совпадает с порядком группы $D_7$. Следовательно, имеется $7!/(2\cdot 7)=360$ способов рассадки людей вокруг стола.
\end{sol_exerc}

\begin{sol_exerc}
В этой задаче без учета симметрий имеются $7!/(2!\cdot 5!)=21$ различных ожерелий. Однако под действием группы $C_7$ симметрий все это множество разбивается на три орбиты, содержащие одинаковое количество элементов. К первой из них относятся ожерелья, в которых два камня синего цвета расположены рядом, ко второй --- ожерелья, в которых эти камни отделены друг от друга одним камнем красного цвета, к третьей --- ожерелья, минимальное расстояние между синими камнями у которых равно двум. Таким образом, имеется три типа различных ожерелий.
\end{sol_exerc}

\begin{sol_exerc}
Без учета симметрий имеются $10!/(3!\cdot 7!)=120$ различных браслетов. Все это множество разбивается на восемь различных орбит. Четыре из них несимметричны относительно отражений, поэтому каждая из них содержит по двадцать браслетов с помеченными камнями. Четыре же из них допускают симметрию отражения: это браслеты, в которых три синих камня примыкают друг к другу, браслеты, в которых эти камни отделены друг от друга одним красным камнем, браслеты, в которых они отделены друг от друга двумя красными камнями, и, наконец, браслеты, в которых два синих камня разделены одним красным камнем, а третий синий камень отделен от каждого из остальных синих камней тремя красными камнями. Как следствие, в каждой из отвечающих таким расположениям орбит содержится по десять браслетов с помеченными камнями. Итого имеется восемь различных браслетов описанного в задаче вида.
\end{sol_exerc}


\begin{sol_exerc}
Заметим, прежде всего, что существует $|X|=2^4=16$ способов окраски вершин квадрата при условии, что все его вершины различны. На этом множестве действует группа $D_4$ симметрий квадрата. Подсчитаем количество орбит элементов множества $X$ под действием группы $D_4$.

В случае, когда все вершины квадрата окрашены в один цвет (например, белый), в орбите содержится всего один элемент --- он переходит в себя под действием любых преобразований. Следовательно, имеются две орбиты, содержащие только по одному элементу множества $X$.

Раскраске, при которой лишь одна вершина окрашена в белый цвет, а остальные окрашены в черный, отвечает орбита, состоящая из четырех элементов. Все они переходят друг в друга при вращениях квадрата вокруг центра его симметрии. То же относится к обратной раскраске, когда лишь одна из вершин окрашена в черный цвет, а остальные --- в белый. Таким образом, в отвечающих этим раскраскам орбитам содержится по четыре элемента.

Оставшееся множество, состоящее из шести раскрасок, также разбивается на две орбиты. В первую из них входят четыре раскраски, у которых соседние пары вершин окрашены в одинаковый цвет. Во второй орбите содержатся две раскраски, в которых одним и тем же цветом окрашиваются противоположно лежащие вершины.  

Таким образом, имеется шесть различных способов раскраски вершин квадрата в не более чем два цвета (см.рис.\ref{fig:square_color}).


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_color}
\caption{Раскраски квадрата в не более чем два цвета}
\label{fig:square_color}
\end{figure}

\end{sol_exerc}

\begin{sol_exerc} 
Разобъем множество $X$ всех триангуляций $(n+2)$-угольников с помеченными вершинами на три блока. В первый блок включим все триангуляции, которые переходят в себя лишь при вращениях на $360^{\circ}$. Во второй блок включим триангуляции, которые переходят в себя при вращениях на $360^{\circ}$ и на $180^{\circ}$. Наконец, к третьему блоку отнесем все триангуляции, переходящие в себя при вращениях на угол, кратный $2\pi/3$. Мощности соответствующих блоков обозначим через $P_n$, $Q_n$ и $R_n$ соответственно. Ясно, что
$$
P_n+Q_n+R_n=C_n,
$$
где $C_n$ --- число Каталана. 

Очевидно, что триангуляции, принадлежащие второму блоку представляют собой, по сути, триангуляции двух $(n/2+2)$-угольников, склеенных по ребру, соединяющему одну из $(n+2)/2$ пар заданного $(n+2)$-угольника. Как следствие, количество таких триангуляций $Q_n=C_{n/2}\cdot (n+2)/2$ в случае четного $n$. В случае нечетного $n$ такие триангуляции отсутствуют. Далее для краткости мы будем записывать этот результат как $C_{[n/2]}\cdot (n+2)/2$, считая, что $C_{[i]}=C_i$ в случае, когда $i$ --- целое число, и ноль в случае, когда $i\notin\Z$. 

Далее, триангуляции третьего блока можно рассматривать как три одинаковые триангуляции $[(n-1)/3+2]$-угольника, приклеенные к трем сторонам центрального равностороннего треугольника в случае, если $(n-1)/3$ есть целое число. Так как в этом случае имеются $(n+2)/3$ различных троек вершин, образующих центральный треугольник, то количество таких триангуляций равно, очевидно, $R_n=C_{[(n-1)/3]}\cdot (n+2)/3$.

Как следствие, количество $P_n$ триангуляций первого блока вычисляется по формуле
$$
P_n=C_n-Q_n-R_n=C_n-C_{[n/2]}\dfrac{(n+2)}{2}-C_{[(n-1)/3]}\dfrac{(n+2)}{3}.
$$

Теперь постараемся учесть симметрию вращения. Под действием группы вращений описанные выше блоки разбиваются на классы эквивалентности --- орбиты $Gx$. Основное наблюдение в данном случае состоит в том, что мощность орбиты в данной задаче напрямую зависит от того, к какому из описанных выше блоков относится выбранный помеченный объект.

Так, в случае, если триангулированный $(n+2)$-угольник с помеченными вершинами относится к первому блоку, то орбитой такого элемента будут все триангулированные многоугольники, полученные из исходного вращением на угол, кратный $2\pi/(n+2)$. Иными словами, мощность орбиты в этом случае будет равна $(n+2)$. В случае, когда триангулируемый $(n+2)$-угольник принадлежит второму блоку, количество элементов в любой орбите уменьшается вдвое по сравнению с предыдущим случаем и оказывается равным $(n+2)/2$. Наконец, для триангулируемых многоугольников из третьего блока мощность орбиты оказывается равной $(n+2)/3$. Поэтому общее количество $f_n$ непомеченных триангуляций с учетом симметрии вращений оказывается равно
$$
f_n=\dfrac{1}{(n+2)}P_n+\dfrac{2}{(n+2)}Q_n+\dfrac{3}{(n+2)}R_n=\dfrac{1}{(n+2)}\left(
P_n+2Q_n+3R_n\right)=\dfrac{1}{(n+2)}\left(C_n+Q_n+2R_n\right).
$$
Подставляя в эту формулу выражения для $Q_n$ и $R_n$, окончательно получаем
$$
f_n=\dfrac{1}{(n+2)}\cdot C_n+\dfrac{1}{2}\cdot C_{[n/2]}+\dfrac{2}{3}\cdot C_{[(n-1)/3]}
$$
(последовательность $A001683$ в энциклопедии последовательностей целых чисел). 

Заметим, что рассмотренная задача эквивалентна перечислению так называемых плоских $2$-деревьев, связана с задачей роста клеток заданной треугольной формы на плоскости, а также с задачей перечисления полиэновых углеводородов.
\end{sol_exerc}



\section{Лемма Бернсайда}

\myitem В предыдущем параграфе мы выяснили, что с формальной точки зрения любой непомеченный объект представляет собой некоторый класс эквивалентности на множестве $X$ всех помеченных объектов данного типа. Отношение же эквивалентности на этом множестве вводится с помощью действия некоторой группы $G$ на множестве $X$. В результате такого действия все множество $X$ разбивается на классы эквивалентности --- орбиты $G/X$. Задача перечисления непомеченных объектов, таким образом, эквивалентна задаче подсчета количества $|G/X|$ всех таких орбит. 

Вообще говоря, подсчет количества орбит сводится к перебору элементов в каждой из таких орбит. Теория групп предлагает еще один, иногда более удобный с практической точки зрения способ определения числа $|G/X|$, опирающийся на так называемую лемму Бернсайда. Для того, чтобы эту лемму сформулировать, нам понадобится ввести целый ряд дополнительных понятий теории групп.

\mysubitem Прежде всего, нам понадобится следующее полезное

\begin{defin} Стабилизатором $G_x$ элемента $x\in X$ называется подмножество элементов группы $G$, оставляющих $x$ неподвижным:
$$
G_x:=\{g\in G \colon g\circ x=x\}.
$$
\end{defin}

Важным свойством стабилизатора является тот факт, что это подмножество оказывается замкнутым относительно действия $\cdot$ в группе $G$. Иными словами, подмножество этих объектов образует \emph{подгруппу} группы $G$.
Действительно,
\begin{enumerate}
\item подмножество $G_x$, очевидно, не пусто --- в него обязательно входит нейтральный элемент $e$ группы $G$: $e\circ x=x$ для любого $x\in X$;
\item для любого $g\in G_x$ обратный ему элемент $g^{-1}$ также принадлежит $G_x$:
$$
\sqsupset \quad g\circ x=x\quad \Longrightarrow \quad (g^{-1}\cdot g)\circ x=g^{-1}\circ x
\quad \Longleftrightarrow \quad x=g^{-1}\circ x;
$$
\item наконец, если $g\in G_x$ и  $h\in G_x$, то и их произведение $g\cdot h$ также принадлежит $G_x$:
$$
(g\cdot h)\circ x=g\circ(h\circ x)=g\circ x=x.
$$
\end{enumerate}

\mysubitem Тот факт, что $G_x$ является подгруппой группы $G$ для любого $x\in X$, позволяет нам построить очень полезное разбиение всех элементов группы $G$ на блоки одинакового размера. Выберем для этого произвольный элемент $g$ группы $G$, и умножим этот элемент на все элементы $h$ нашей подгруппы $H\equiv G_x$. В результате мы получим подмножество
$$
g\cdot H:=\{g\cdot h\mid h\in H\}.
$$
Перебирая разные элементы $g$ группы $G$, мы получим целый набор подмножеств вида $g\cdot H$. Оказывается, что этот набор и задает нам разбиение группы $G$ на блоки. 

Именно, предположим, что у двух подмножеств $g_1\cdot H$ и $g_2\cdot H$, порожденных двумя различными элементами $g_1$ и $g_2$ группы $G$, имеется общий элемент $g\in G$. Это означает, что существуют элементы
$$
h_1\in H\colon \quad g=g_1\cdot h_1,\qquad \text{и} \qquad h_2\in H\colon\quad g=g_2\cdot h_2.
$$
Следовательно,
$$
g_1\cdot h_1=g_2\cdot h_2\qquad \Longrightarrow\qquad g_1=g_2\cdot (h_2\cdot h_1^{-1})\qquad \text{и}\qquad
g_2=g_1\cdot (h_1\cdot h_2^{-1}).
$$
Но подгруппа $H$ замкнута относительно действия в группе, так что $h_2\cdot h_1^{-1}=:h_3\in H$ и $h_2\cdot h_1^{-1}=:h_4\in H$, и поэтому $g_1\in g_2\cdot H$ и $g_2\in g\cdot H$. Иными словами, любые два подмножества вида $g_1\cdot H$ и $g_2\cdot H$ либо не пересекаются между собой, либо совпадают.

Более того, пусть подгруппа $H$ содержит $k$ элементов $h_1=e,h_2,\ldots,h_k$. Так как для любого $g\in G$ элементы 
$$
g\cdot h_i\neq g\cdot h_j\qquad \text{в случае, если}\qquad h_i\neq h_j,
$$
то все элементы $g\cdot h_i$ подмножества 
$$
g\cdot H=\{g\cdot h_1,g\cdot h_2,\ldots,g\cdot h_k\}
$$
отличны друг от друга. Как следствие, любой блок вида $g\cdot H$ для любого $g\in G$ содержит то же количество элементов, что и сама подгруппа $H$. Тем самым мы и доказали, что с помощью подгруппы $H$ мы можем разбить группу $G$ на блоки $g\cdot H$ одинакового размера. 

Каждый такой блок $g\cdot H$ называется смежным классом $G$ по $H$, а само множество таких блоков называется множеством смежных классов $G$ по $H$ и обозначается $G/H$. Так как количество элементов в каждом смежном классе одинаково и равно $|H|$, то количество элементов $|G|$ в группе связано с количеством $|G/H|$ смежных классов следующим полезным соотношением:
$$
|G|=|H|\cdot |G/H|.
$$

\mysubitem Вернемся к введенному выше понятию стабилизатора $G_x$ элемента $x\in X$. Оказывается, имеется тесная связь между орбитами $Gx$ и стабилизаторами $G_x$ элемента $x\in X$. Именно, справедлива следующая

\begin{theor} \label{theor:equiv_orb_fact}
Для любого $x\in X$ имеется взаимно-однозначное соответствие между
\begin{enumerate}
\item множеством всех элементов орбиты элемента $x$, т.е. множеством
$$
Gx=\{y\in X\,|\,\exists\,g\in G:\,\,g\circ x=y\},
$$
\item и фактор-множеством $G/G_x$, т.е. множеством смежных классов $G$ по стабилизатору $G_x$,
\end{enumerate}
при котором любой точке $y=g\circ x$ орбиты $Gx$ отвечает некоторый смежный класс $g\cdot G_x$ (т.е. элемент фактор-множества $G/G_x$). 
\end{theor}

\evidp По сути, нам необходимо доказать очень простой факт, а именно, если $g_1$ и $g_2$ принадлежат одному и тому же смежному классу, то они переводят $x$ в один и тот же элемент $y\in X$, и наоборот. А этот факт доказывается элементарно:
$$
\sqsupset \quad g_2\in g_1\cdot G_x\quad \Longleftrightarrow \quad g_1^{-1}\cdot g_2\in G_x\quad
\Longleftrightarrow \quad (g_1^{-1} \cdot g_2)\circ x=x \quad \Longleftrightarrow \quad
g_2\circ x=g_1\circ x=:y\in X.
$$
По другому доказанный факт можно переформулировать следующим образом: различным точкам $y\in Gx$ орбиты отвечают различные смежные классы $g\cdot G_x$.\qed

\begin{rem}
В частном случае, когда стабилизатор $G_x$ состоит из единственного нейтрального элемента $e$, имеет место взаимно-однозначное соответствие между всеми элементами орбиты $Gx$ и всеми элементами группы $G$.
\end{rem}

\begin{conseq} Имеет место следующее равенство:
\begin{equation}
\label{eq:orbits_eqv_classes}
|G|=|Gx|\cdot |G_x|.
\end{equation}
\end{conseq}

\evidp Действительно, мы выше показали, что для подгруппы $G_x\equiv H$ справедливо равенство вида
$$
|G|=|G/H|\cdot |H|=|G/G_x|\cdot |G_x|.
$$
Доказанная нами теорема \ref{theor:equiv_orb_fact} устанавливает взаимно-однозначное соответствие между элементами множеств $G/G_x$ и $Gx$, из которого, в частности, следует равенство $|G/G_x|=|Gx|$. Следовательно, для любого $x\in X$ верно соотношение (\ref{eq:orbits_eqv_classes}).
\qed

\myitem Теперь мы, наконец, готовы сформулировать и доказать лемму Бернсайда.

\mysubitem  Зафиксируем некоторый элемент $g$ группы $G$. Обозначим через $X^g$ подмножество элементов множества $X$, остающихся неподвижными под действием этого $g\in G$:
$$
X^g:=\{x\in X:\,\,|\,\,g\circ x=x\}.
$$

\begin{lemm}[Бернсайд] 
Количество орбит, т.е. мощность фактор-множества $X/G$, может быть рассчитано по формуле
\begin{equation}
\label{eq:Bernsaid}
|X/G|=\dfrac{1}{|G|}\sum_{g\in G}|X^g|.
\end{equation}
\end{lemm}

\evidp Сосчитаем количество всех пар $(g,x)$, $g\in G$, $x\in X$, таких, что $g\circ x=x$, т.е. мощность множества
$$
\{(g,x)\in G\times X\,\,|\,\, g\circ x=x\}.
$$
Сделать это можно двумя различными способами. В первом из них для любого фиксированного элемента $g$ группы $G$ подсчитаем количество $|X^g|$ элементов множества $X$, остающихся неподвижными под действием $G$. При таком способе подсчета количество искомых пар оказывается равным
$$
|\{(g,x)\in G\times X\mid g\circ x=x\}|=\sum_{g\in G}|X^g|.
$$
Теперь поступим наоборот, а именно, для любого фиксированного элемента $x$ множества $X$ сосчитаем количество элементов группы $g$, оставляющих этот элемент $x$ неподвижным. Из определения стабилизатора $G_x$ элемента $x\in X$ мы получаем, что в этом случае
$$
|\{(g,x)\in G\times X\mid g\circ x=x\}|=\sum_{x\in X}|G_x|.
$$
Воспользуемся теперь равенством (\ref{eq:orbits_eqv_classes}). Согласно этому равенству, мощность стабилизатора $G_x$ равна $|G_x|=|G|/|Gx|$, и поэтому
$$
\sum_{g\in G}|X^g|=|G|\,\sum\limits_{x\in X}\dfrac{1}{|Gx|}.
$$

Осталось доказать, что стоящая в правой части последнего равенства сумма равна $|X/G|=:k$. Мы знаем, что под действием группы $G$ множество $X$ разбивается на $k$ попарно непересекающихся классов эквивалентности $Gx_i$, $i=1,\ldots,k$. Следовательно, мы можем так сгруппировать слагаемые в сумме $\sum_{x\in X}1/|Gx|$, чтобы все входящие в $i$-ю группу слагаемые отвечали элементам $x$ из одного и того же класса эквивалентности $Gx_i$:
$$
\sum_{x\in X}\dfrac{1}{|Gx|}=\sum_{i=1}^k\,\sum_{x\in Gx_i}\dfrac{1}{|Gx_i|}.
$$
Теперь заметим, что при любом фиксированном $i$ все слагаемые внутренней суммы одинаковы и равны $1/|Gx_i|$, а количество самих слагаемых совпадает с количеством элементов в $i$-м классе эквивалентности, то есть равно все тому же $|Gx_i|$:
$$
\sum_{x\in Gx_i}\dfrac{1}{|Gx_i|}=\dfrac{1}{|Gx_i|}\sum_{x\in Gx_i}1=\dfrac{|Gx_i|}{|Gx_i|}=1. 
$$
Отсюда мы и получаем, что
$$
\sum_{x\in X}\dfrac{1}{|Gx|}=\sum_{i=1}^k1=k=|X/G|.
$$
\qed

\begin{rem} Очевидно, что нейтральный элемент $e$ группы $G$ оставляет неподвижным любой элемент множества $X$, и поэтому всегда $|X^e|=|X|$. Если любой другой элемент $g$ группы $G$ не оставляет на месте ни один элемент $x\in X$, то тогда для любого $g\in G$, $g\neq e$, мощность $|X^g|=0$, и мы из (\ref{eq:Bernsaid}) получаем знакомую нам формулу
$$
|X/G|=\dfrac{|X|}{|G|}.
$$
\end{rem}



\mysubitem Практический смысл леммы Бернсайда состоит в следующем. Количество элементов в группе $G$, как правило, меньше количества элементов в множестве $X$, на котором эта группа действует. Поэтому на практике часто оказывается легче перебрать все элементы $g\in G$ и посмотреть, какие из элементов $x\in X$ остаются под действием этих элементов неподвижными, чем перебирать все $x\in X$ и считать для каждого такого $x$ количество элементов в его орбите $Gx$.

\begin{examp} 
Еще раз рассмотрим задачу о подсчете геометрически различных способов окраски вершин правильного треугольника, но на этот раз подсчитаем количество способов раскраски этих вершин в не более чем десять цветов.
\end{examp}

\decis Заметим сразу же, что в этой задаче имеется $10^3$ способов окраски вершин треугольника в не более чем десять цветов. Иными словами, без использования леммы Бернсайда нам бы пришлось перебирать всю тысячу элементов множества $X$ помеченных окрашенных объектов, и для каждого элемента $x\in X$ вычислять количество элементов в орбите $Gx$ этого элемента под действием группы $G$.

Напротив, количество элементов в группе $G=D_3$ симметрий треугольника, действующей на множестве $X$ помеченных объектов, невелико и равно шести. Поэтому в данной задаче легче воспользоваться леммой Бернсайда, то есть подсчитать количество $X^g$ элементов множества $X$, остающихся неподвижными под действием фиксированного элемента $g$ группы $G=D_3$.  

Начнем с нейтрального элемента группы $g=e$. Под действием $e\in G$ любой элемент множества $X$ остается неподвижным. Поэтому, $|X^e|=|X|=10^3=1000$.

Элементы $a$ и $b$ группы, отвечающие вращениям треугольника вокруг его центра симметрии на углы в $120^\circ$ и $240^\circ$ соответственно, оставляют неподвижными только десять элементов множества $X$ --- раскраски, в которых все вершины треугольника окрашены в один цвет. Следовательно, мощности $|X^a|$ и $|X^b|$ для этих элементов группы равны $10$.

Осталось рассмотреть вращения $c,d,f\in G$ треугольника вокруг осей $l_i$, проходящих через выбранную вершину $i$, $i=1\ldots 3$, треугольника и центр противоположной ей грани. При таких вращениях остаются неподвижными элементы множества $X$, соответствующие окраске вершины $i$ в любой из двух цветов, а двух оставшихся вершин --- в один общий цвет. Как следствие, мощности множеств $X^c$, $X^d$, $X^f$ одинаковы и равны $10^2$.

Теперь мы можем воспользоваться равенством (\ref{eq:Bernsaid}) для подсчета искомого количества орбит:
$$
|X/G|=\dfrac{1}{6}[10^3+2\cdot 10^2+3\cdot 10^1]=\dfrac{1320}{6}=220.
$$



\section*{Упражнения}


\begin{exerc} Подсчитать с помощью леммы Бернсайда количество геометрически различных способов окраски вершин квадрата в не более чем два цвета.
\end{exerc}

\begin{exerc} \label{gr_sim_cube} Описать группу симметрий куба.
\end{exerc}

\begin{exerc} Подсчитать с помощью леммы Бернсайда количество геометрически различных способов окраски граней куба в не более чем два цвета.
\end{exerc}

\section*{Решение упражнений}

\begin{sol_exerc}
Под действием нейтрального элемента группы все $2^4=16$ элементов множества $X$ остаются неподвижными. Повороты на $90^{\circ}$ и $270^{\circ}$ оставляют на месте квадраты, чьи вершины окрашены только в белый или только в черный цвета. Для поворота на $180^{\circ}$ к ним добавляются два квадрата, противоположные вершины которых окрашены в одинаковый цвет. Отражения относительно оси, проходящей через середины противоположных сторон квадрата, оставляют неподвижными четыре квадрата --- два квадрата, все вершины которых окрашены в один и тот же цвет, а также два квадрата, у которых в один и тот же цвет окрашена верхняя и нижняя пары вершин. Наконец, отражения относительно осей, проходящих через противоположные вершины квадрата, переводят в себя восемь квадратов --- это все квадраты, не лежащие на оси отражения вершины которых окрашены в один и тот же цвет. Следовательно, по лемме Бернсайда имеем
$$
|X/G|=\dfrac{1}{8}[2^4+2\cdot 2+2^2+2\cdot 2^2 +2\cdot 2^3]=6.
$$
\end{sol_exerc}


\begin{sol_exerc}
Как и в любой группе, в группе $G$ симметрий куба существует нейтральный элемент. Кроме того, в $G$ существует три вращения по часовой и три вращения против часовой стрелке относительно трех осей, проходящих через центры противоположных граней, на $90^{\circ}$. Далее, имеются три вращения на $180^{\circ}$ относительно тех же осей. Вращения куба относительно четырех осей, проходящих через противоположные вершины куба, на $120^{\circ}$ и $240^{\circ}$ дают еще $8$ элементов группы $G$. Наконец, имеются еще шесть вращений куба на $180^{\circ}$ относительно осей, проходящих через центры противоположных ребер куба. Итого получаем 
$$
1+2\cdot 3+3+2\cdot 4+6=24
$$
элемента группы $G$.
\end{sol_exerc}


\begin{sol_exerc}
Мощность множества $X$ в данной задаче равна $2^6=64$. Под действием нейтрального элемента группы все эти элементы остаются на своем месте. Повороты на $90^{\circ}$ и $270^{\circ}$ относительно осей, проходящих через центры противоположных граней куба, оставляют на месте $2^3=8$ элементов множества $X$, отвечающих произвольной окраске противоположных граней куба, а также окраске в один из двух цветов оставшихся четырех граней куба. Повороты на $180^{\circ}$ относительно тех же осей оставляют на месте уже $2^4$ элементов: здесь теперь в один и тот же цвет должны быть окрашены две пары противоположных граней, переходящих друг в друга при вращениях. 

Вращения на $120^{\circ}$ и $240^{\circ}$ относительно осей, проходящих через противоположные вершины куба, переводят окрашенный куб в себя лишь в случае, если все три примыкающие к данной вершине грани окрашены в один и тот же цвет. Следовательно, имеется $2^2=4$ окраски куба, переходящих в себя при любом из восьми подобных вращений.

Наконец, шесть вращений куба на $180^{\circ}$ относительно осей, проходящих через центры противоположных ребер куба, переводят окрашенный куб в себя в том случае, если две пары прилегающих к ребрам граней, а также пара перпендикулярных к ним граней окрашена в один и тот же цвет. Это дает для каждого из шести вращений $2^3=8$ вариантов.

Подводя итоги, по лемме Бернсайда имеем
$$
|X/G|=\dfrac{1}{24}[2^6+6\cdot 2^3+3\cdot 2^4+8\cdot 2^2+6\cdot 2^3]=10
$$
геометрически различных способов окраски граней куба в не более чем два цвета.
\end{sol_exerc}

\section{Цикловой индекс группы перестановок. Теория Ред\-фил\-да-Пойа}

\myitem Итак, при подсчете количества орбит удобно использовать лемму Бернсайда. Пойа и Редфилд заметили, что  для некоторого важного класса задач этот подсчет можно упростить.

\mysubitem Именно, пусть у нас имеется некоторая геометрическая фигура $\Gamma$, и пусть $\tilde{X}$ есть множество каких-то элементов фигуры $\Gamma$ (например, множество вершин, или ребер, или граней этой фигуры). Рассмотрим задачу о подсчете количества геометрически различных способов окраски элементов $x\in\tilde{X}$, $|\tilde{X}|=n$, этой геометрической фигуры  $\Gamma$ в не более чем $k$ цветов. Мы знаем, что для решения этой задачи нужно ввести множество $X$ различных способов окраски помеченных элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$ в не более чем в $k$ цветов (мощность $|X|$ этого множества равна, очевидно, $k^n$), рассмотреть действие группы $G$ симметрий геометрического объекта $\Gamma$ на множестве $X$, а затем подсчитать количество $|X/G|$ орбит элементов $X$ под действием группы $G$ --- либо непосредственно, либо с помощью леммы Бернсайда. 

\mysubitem Заметим, однако, что та же самая группа $G$ симметрий фигуры $\Gamma$ действует и на значительно более узком множестве $\tilde{X}$ \emph{неокрашенных} элементов этой фигуры. Такое действие задает нам естественный гомоморфизм 
\begin{equation}
\label{est_izom}
\phi\colon G\to S_n
\end{equation}
группы $G$ в симметрическую группу $S_n$, $n=|\tilde{X}|$ всех перестановок $n$-множества. Образ $\Sigma_G$ этого гомоморфизма называется обычно группой перестановок элементов множества $\tilde{X}$. Так вот, оказывается, все, что нужно знать для решения исходной задачи подсчета количества $|X/G|$ орбит --- это так называемый цикловой индекс $Z_{\Sigma_G}$ группы перестановок множества $\tilde{X}$. 

\myitem Введем понятие циклового индекса произвольной подгруппы $\Sigma$ группы $S_n$. 

\mysubitem Напомним, что в предыдущей главе мы ввели цикловой индекс множества $S_n$ всех перестановок $n$-элементного множества $[n]$
$$
Z_n(x_1,x_2,\ldots,x_n)=\dfrac{1}{n!}\tilde{Z}_n(x_1,x_2,\ldots,x_n)=
\dfrac{1}{n!}\sum\limits_{1\cdot i_1+2\cdot i_2+\ldots+n\cdot i_n=n}x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}
$$
как коэффициент при $z^n$ в разложении экспоненциальной производящей функции 
$$
C(z)=\exp\Bigl(x_1\dfrac{z^1}{1}+x_2\dfrac{z^2}{2}+\ldots+x_n\dfrac{z^n}{n}+\ldots\Bigr)
$$
по степеням формальной переменной $z$:
$$
C(z)=\sum\limits_{n=0}^{+\infty}\tilde{Z}_n(x_1,x_2,\ldots,x_n)\dfrac{z^n}{n!}=
\sum\limits_{n=0}^{+\infty}Z_n(x_1,x_2,\ldots,x_n)\,z^n.
$$ 
Мы вывели также как явные, так и рекуррентные формулы для вычисления цикловых индексов $Z_n(x_1,x_2,\ldots,x_n)$, а также объяснили их комбинаторный смысл. 

Так, наличие слагаемого вида $x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}$  в выражении для $Z_n(x_1,x_2,\ldots,x_n)$ означает, что в группе $S_n$ имеется перестановка $\sigma$, которая раскладывается в произведение $i_1$ циклов единичной длины, $i_2$ циклов длины $2$ и так далее. 

\begin{defin} Если перестановка $\sigma$ представляется в виде произведения $i_1$ циклов единичной длины, $i_2$ циклов длины $2$ и так далее, то говорят, что такая перестановка имеет цикловой тип $\{i_1,i_2,\ldots,i_n\}.$ 
\end{defin} 

Таким образом,  любое слагаемое вида $x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}$ в цикловом индексе $\tilde{Z}_n(x_1,x_2,\ldots,x_N)$ определяет нам цикловой тип перестановки $\sigma\in S_n$. Числовой же коэффициент при мономе вида $x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}$ показывает, сколько существует перестановок $\sigma$ в симметрической группе $S_n$, имеющих заданный цикловой тип  $\{i_1,i_2,\ldots,i_n\}.$ 



\mysubitem Рассмотрим в качестве примера цикловой индекс группы $S_n$ перестановок для случая $n=3$. В главе 4 мы показали, что указанный цикловой индекс имеет вид
$$
Z_3(x_1,x_2,x_3)=\dfrac{1}{3!}[x_1^3+3x_1x_2+2x_3].
$$
Комбинаторный смысл коэффициентов в этом выражении следующий: множество всех перестановок $3$-элементного множества содержит тождественную перестановку $(1)(2)(3)$ (слагаемое $x_1^3$, отвечающее произведению трех циклов единичной длины), три перестановки $(1\,2)(3),$ $(1\,3)(2),$ $(2\,3)(1),$ представляющие собой произведение цикла длины два на цикл длины один (слагаемое $3x_1x_2$), а также две перестановки $(1\,2\,3)$ и $(1\,3\,2),$ состоящие из единственного цикла длины три (слагаемое $2x_3$). 

\mysubitem Рассмотрим теперь произвольную подгруппу $\Sigma$ симметрической группы $S_n$. По аналогии со всей группой, для подгруппы $\Sigma$ также можно ввести цикловой индекс $Z_{\Sigma}(x_1,x_2,\ldots,x_n)$ по формуле
$$
Z_{\Sigma}(x_1,x_2,\ldots,x_n)=
\dfrac{1}{|\Sigma|}\sum\limits_{\sigma\in \Sigma}x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n},
$$
где $\{i_1,i_2,\ldots,i_n\}$ есть цикловой тип перестановки $\sigma\in \Sigma$. Комбинаторный смысл коэффициентов при мономах вида $x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}$ в этом выражении абсолютно тот же самый, что и в случае циклового индекса множества $S_n$ всех перестановок $n$-элементного множества --- эти коэффициенты показывают,  сколько перестановок в $\Sigma$ имеют один и тот же цикловой тип. 

Так, например, цикловой индекс циклической подгруппы $C_3$ симметрической группы $S_3$ имеет вид
$$
Z_{C_3}(x_1,x_2,x_3)=\dfrac{1}{3}[x_1^3+2x_3].
$$
Действительно, в эту подгруппу входят только единичная перестановка, чей цикловой тип равен $\{1,0,0\}$, а также две перестановки $(1\,2\,3)$ и $(1\,3\,2)$, цикловые типы которых имеют вид $\{0,0,1\}$. 


\myitem Вернемся к задачам о раскраске элементов геометрических фигур и объясним, как использование циклового индекса группы $\Sigma_G$ помогает в решении этих задач.

\mysubitem Выберем какой-то элемент $\sigma_g$ группы перестановок $\Sigma_G$ элементов множества $\tilde{X}$. Согласно лемме Бернсайда, для подсчета количества орбит нам нужно при любом таком $\sigma_g$ подсчитать количество способов окраски элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$, при которых окрашенная фигура переходит в себя под действием $g\in G$. Давайте поймем, как при этом должны быть окрашены элементы множества $\tilde{X}$. 

Рассмотрим, например, задачу о раскраске вершин квадрата $\Gamma$ в не более чем два цвета. В этой задаче в качестве $G$ выступает группа $D_4$ симметрий квадрата, в качестве $\tilde{X}$ --- множество $\{1,2,3,4\}$ помеченных вершин этого квадрата. Пусть $g\in D_4$ есть вращение квадрата $\Gamma$ на $180^\circ$. Образом этого элемента при гомоморфизме $D_4\to S_4$ является перестановка множества вершин квадрата следующего вида: $\sigma_g=(1\,3)(2\,4)$.

Предположим теперь, что мы окрасили вершины $1$ и $3$ в разные цвета. Очевидно, что при таком способе окраски вершин квадрата окрашенная фигура $\Gamma$ под действием $g$ в себя не перейдет ---  в результате поворота изменится и цвет вершины $1$, и цвет вершины $3$. Для того, чтобы этого не произошло, необходимо, чтобы вершины $1$ и $3$ были окрашены в одинаковый цвет. Понятно, что аналогичное условие должно быть выполнено и для вершин, входящих во второй цикл --- вершины $2$ и $4$ также должны быть окрашены в один и тот же цвет.

Заметим теперь, что первую пару вершин (вершины $1$ и $3$) мы можем окрасить в любой из двух цветов, и вторую пару вершин (вершины $2$ и $4$) мы также можем окрасить в любой из двух цветов вне зависимости от того, в какой цвет выкрашена первая пара вершин. Следовательно, существует $2\cdot 2=4$ способа окраски вершин квадрата $\Gamma$, при которых окрашенный квадрат перейдет в себя в результате его поворота на $180^{\circ}$. Все эти четыре способа изображены на рис.\ref{fig:square_fixed}.

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_fixed}
\caption{Неподвижные точки для поворота на $180 ^{\circ}$}
\label{fig:square_fix}
\end{figure}

Понятно теперь, что те же рассуждения справедливы и в общем случае. Пусть, например, под действием перестановки $\sigma_g$ элемент $x_1\in\tilde{X}$ переходит в элемент $x_2\in\tilde{X}$. Если мы эти элементы окрасим в разные цвета, то в результате перестановки $\sigma_g$ цвет вершины $x_2$ изменится, и окрашенная таким образом фигура $\Gamma$ в себя не перейдет. Иными словами, для того, чтобы окрашенная фигура $\Gamma$ перешла в себя под действием элемента $g\in G$, необходимо и достаточно, чтобы все элементы множества $\tilde{X}$, входящие в один и тот же цикл перестановки $\sigma_g\in \Sigma_G$, были окрашены в один и тот же цвет. 

Предположим теперь, что перестановка $\sigma_g$ имеет цикловой тип $\{i_1,i_2,\ldots,i_n\}.$ Это, в частности, означает, что эта перестановка может быть представлена в виде произведения $m=i_1+i_2+\ldots+i_n$ циклов. Каждый такой цикл независимо от других может быть окрашен в любой из $k$ цветов. Следовательно, существует ровно $k^m$ способов окраски элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$, при которых окрашенная фигура переходит в себя под действием элемента $g\in G$. 

Общее же количество геометрически различных способов окраски элементов $x\in\tilde{X}$ фигуры $\Gamma$ в не более чем $k$ цветов можно, согласно лемме Бернсайда, определить по формуле
$$
|X/G|=\dfrac{1}{|\Sigma_G|}\sum\limits_{\sigma_g\in \Sigma_G}k^{i_1+\ldots+i_n},
$$
где $\{i_1,i_2,\ldots,i_n\}$ --- цикловой тип перестановки $\sigma_g$. 

Все, что теперь нам остается --- это заметить, что полная информация о цикловом типе всех входящих в $\Sigma_G$ перестановок содержится в цикловом индексе $Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)$ группы $\Sigma_G$. С учетом этого обстоятельства мы можем окончательно сформулировать следующий результат.

\begin{lemm}[Редфилд, Пойа]\label{lemm_Redf_Polya}
Количество орбит элементов множества $X$ под действием группы $G$ в задаче, связанной с раскраской элементов $x\in \tilde{X}$ геометрической фигуры $\Gamma$ в не более чем $k$ цветов, рассчитывается по формуле
\begin{equation}
\label{formula_Redf_Polya}
|X/G|=Z_{\Sigma_G}(k,\ldots,k)=\dfrac{1}{|\Sigma_G|}\sum\limits_{\sigma_g\in \Sigma_G}k^{i_1+\ldots+i_n},\qquad \qquad n=|\tilde{X}|,
\end{equation}
где $\{i_1,i_2,\ldots,i_n\}$ --- цикловой тип перестановки $\sigma_g\in\Sigma_G$.
\end{lemm}

\mysubitem В качестве примера дорешаем задачу о раскраске вершин квадрата. Несложно показать (см. Упражнение \ref{ex_cicl_ind_D_4}), что цикловой индекс группы $D_4$ симметрии квадрата (а точнее, образа $\Sigma_{D_4}$ этой группы при гомоморфизме $\phi:\,D_4\to\,S_4$) имеет вид 
\begin{equation}
\label{cicl_ind_D_4}
Z_{\Sigma_{D_4}}(x_1,x_2,x_3,x_4)=\dfrac{1}{8}[x_1^4+2x_1^2x_2+3x_2^2+2x_4].
\end{equation}
Следовательно, количество геометрически различных способов окраски вершин квадрата в не более чем $2$ цвета равно
$$
|X/D_4|=Z_{\Sigma_{D_4}}(2,2,2,2)=\dfrac{1}{8}[2^4+2\cdot2^2\cdot 2+3\cdot 2^2+2\cdot 2]=6.
$$


\myitem Лемма \ref{lemm_Redf_Polya} была сформулирована Рэдфилдом \cite{Redfild} в 1927 году и, независимо от него, Пойа \cite{Polya_paper},\cite{Polya} в 1937 году. Базируясь на этом замечательном результате, Рэдфилд и Пойа построили свою теорию перечисления непомеченных объектов. При этом работа Рэдфилда долгое время оставалась незамеченной, тогда как на работу Пойа сразу обратили внимание. Более того, Пойа очень удачно развил этот результат, подключив к этой науке теорию производящих функций. В результате теория перечисления Пойа стала одним из наиболее мощных инструментов современной перечислительной комбинаторики. К ее изучению мы и перейдем в следующих параграфах. Сейчас же мы опишем предложенный Пойа весьма полезный для этой теории способ формализации понятия раскраски элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$. 

\mysubitem Итак, пусть имеется некоторая геометрическая фигура $\Gamma$, пусть $\tilde{X}$ есть некоторое $n$-множество помеченных элементов этой фигуры $\Gamma$, и пусть $Y$ есть некоторое $k$-множество цветов, в которые мы собираемся окрашивать элементы $n$-множества $\tilde{X}$. Тогда любое отображение
$$
f\colon \tilde{X}\,\,\to \,\,Y
$$
задает нам некоторую окраску элементов множества $\tilde{X}$ цветами из множества $Y$. 

Так, например, окраску вершин квадрата $1$ и $3$ в белый цвет, $2$ и $4$ --- в черный цвет описывает функция вида $f(x_1)=f(x_3)=y_1$, $f(x_2)=f(x_4)=y_2$. Квадрату, все вершины которого окрашены в белый цвет, отвечает функция $f$, у которой $f(x_i)=y_1$ для всех $i=1,\ldots,4$. 

При таком подходе множество $X$ всех помеченных элементов фигуры $\Gamma$, окрашенных в не более чем $k$ цветов, совпадает с множеством $Y^{\tilde{X}}$ всех отображений $f:\tilde{X}\to Y$. 

\mysubitem Пусть теперь на множестве $\tilde{X}$ задано некоторое действие $\circ$ группы $G$. Оказывается, что это действие индуцирует действие $\bullet$ группы $G$ на множестве $Y^{\tilde{X}}$. Именно, положим по определению
\begin{equation}
\label{induce_action}
(g\bullet f)(x):=f(g^{-1}\circ x)\qquad \forall\,x\in\tilde{X}.
\end{equation}
Определенный таким образом оператор $\bullet$ удовлетворяет как свойству тождественности $e \bullet f=f\quad\forall\,f\in X$, так и свойству ассоциативности $g\bullet (h \bullet f)=(g\cdot h)\bullet f$. Действительно, для любого $x\in\tilde{X}$ имеем
$$
(e \bullet f)(x)\eqdef f(e^{-1}\circ x)=f(e\circ x)=f(x),
$$
$$
g\bullet (h \bullet f)(x)\eqdef (h \bullet f)(g^{-1}\circ x)\eqdef f(h^{-1}\circ (g^{-1}\circ x))=f((h^{-1}\cdot g^{-1})\circ x)=
f((g\cdot h)^{-1}(x)\eqdef ((g\cdot h)\bullet f)(x).
$$ 

\begin{rem}
Согласно определению (\ref{induce_action}), действие элемента $g\in G$ на функцию $f(x)$ эквивалентно действию не самого элемента $g$ на аргумент $x$, а действию на $x$ обратного к $g$ элемента $g^{-1}$ элемента группы $G$. 
Несмотря на кажущуюся сложность, такое определение действия довольно-таки естественно. Так, мы еще с курса элементарного математического анализа привыкли к тому, что если нам задана функция $y=f(x)=x^2$, то функция $f(x-a)=(x-a)^2$ аргумента, сдвинутого на $a$ \emph{влево,} есть сдвиг исходной функции $f(x)=x^2$ как целого на расстояние, равное $a$, \emph{вправо.} И, кстати сказать, этот пример есть также пример действия --- действия группы $G=T_a$ трансляций на некотором множестве функций $f(x)$. 
\end{rem}

\mysubitem Переформулируем теперь основной результат (\ref{formula_Redf_Polya}) теории Редфилда-Пойа на языке отображений $f:\tilde{X}\to Y$. 

В лемме Бернсайда нам необходимо cосчитать для каждого $g\in G$ количество элементов множества $X$, остающихся неподвижными под действием этого $g$. Элементы $f$ множества $Y^{\tilde{X}}$, остающиеся неподвижными под действием элемента $g\in G$ --- это все отображения, у которых для любого $x\in\tilde{X}$ 
\begin{equation}
\label{cond_Berns_Polya}
(g\bullet f)(x)=f(g^{-1}\circ x)=f(x).
\end{equation}

Равенство (\ref{cond_Berns_Polya}) выполняется для функции $f\in Y^{\tilde{X}}$ тогда и только тогда, когда значения этой функции одинаковы на любом цикле перестановки $\sigma_{g^{-1}}=\sigma_g^{-1}\in\Sigma_G$. Отсюда, в частности, следует, что для заданного $g\in G$ количество таких функций равно $|Y|^m=k^m$, где $m$ --- количество циклов в перестановке $\sigma_g^{-1}$. 

Учитывая теперь, что количество циклов и их тип у перестановок $\sigma$ и $\sigma^{-1}$ совпадают, а также то, что вся информация о цикловом типе перестановок группы $\Sigma_G$, в том числе и информация о количестве циклов таких перестановок, содержится в цикловом индексе
$$
Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)=
\dfrac{1}{|\Sigma_G|}\sum\limits_{\sigma\in \Sigma_G}x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}
$$
группы $\Sigma_G$, получаем окончательно следующий результат. 

\begin{lemm}\label{cons_lemm_Redf_Polya}
Количество отображений $f\colon \tilde{X}\to Y$, описывающих геометрически различные способы окраски элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$ цветами из множества $Y$, рассчитывается по формуле
\begin{equation}
\label{cons_form_lemm_Redf_Polya}
|Y^{\tilde{X}}/G|=Z_{\Sigma_G}(k,\ldots,k)=\dfrac{1}{|\Sigma_G|}\sum\limits_{\sigma_g\in \Sigma_G}k^{i_1+\ldots+i_n},\qquad \qquad k=|Y|,\quad n=|\tilde{X}|,
\end{equation}
$\{i_1,i_2,\ldots,i_n\}$ --- цикловой тип перестановки $\sigma_g\in\Sigma_G$.
\end{lemm}


\myitem В заключение данного параграфа рассмотрим чрезвычайно важное приложение описанных выше результатов --- задачу подсчета всех непомеченных простых графов на $n$ вершинах.

\mysubitem Рассмотрим вначале произвольный простой граф, построенный на $n$  помеченных вершинах. Ранее мы говорили, что любой такой граф можно отождествлять с некоторым подмножеством множества, состоящего из всех $\BCf{n}{2}$ пар помеченных вершин данного графа. Однако для решения задачи перечисления всех непомеченных простых графов нам понадобится еще одно, не менее удобное описание простого графа, построенного на $n$ помеченных вершинах. Именно, любой такой граф можно рассматривать как полный граф $K_{n}$, каждое ребро которого окрашено либо в черный, либо в белый цвет. Первый вариант окраски ребра реализуется в том случае, если в исходном графе соответствующая пара вершин соединена ребром. В противном случае реализуется второй вариант окраски. 

Такое описание позволяет нам для решения поставленной задачи воспользоваться теорией Редфилда-Пойа. Действительно, в роли геометрической фигуры $\Gamma$ в данной задаче выступает полный граф $K_{n}$. Множество $\tilde{X}$ его помеченных элементов есть множество всех $\BCf{n}{2}$ пар помеченных вершин графа $K_n$. Множество $Y$ цветов состоит в этом случае из двух элементов. Наконец, любой простой граф, построенный на $n$ помеченных вершинах, отождествляется с одним из элементов множества $X$ окрашенных ребер графа $K_n$. 

Группой симметрий полного графа $K_n$ является симметрическая группа $S_n$ перестановок $n$ помеченных вершин этого графа. Действие группы $S_n$ на множестве $X$ окрашенных ребер графа $K_n$ разбивает это множество на классы эквивалентности --- орбиты элементов множества $X$ под действием группы $S_n$. Любая такая орбита представляет собой некоторый непомеченный граф. Задача перечисления всех непомеченных графов в такой постановке сводится к задаче подсчета количества $|X/S_n|$ орбит элементов множества $X$ под действием группы $S_n$.

\mysubitem Как следует из леммы Редфилда-Пойа, для подсчета количества $|X/S_n|$ орбит нам необходимо описать действие группы $S_n$ на $\BCf{n}{2}$-элементном множестве $\tilde{X}$ ребер полного графа $K_n$, а точнее, сосчитать цикловой индекс группы $\Sigma_{S_n}$ перестановок этого множества  $\tilde{X}$. Покажем, как это делать, для нескольких конкретных значений параметра $n$.

\mysubitem В полном графе $K_3$ количество ребер совпадает с количеством вершин. Как следствие, группа $\Sigma_{S_3}$ перестановок множества $\tilde{X}$ ребер этого графа совпадает с симметрической группой $S_3$ перестановок множества вершин графа $K_3$. Поэтому
$$
Z_{\Sigma_{S_3}}(x_1,x_2,x_3)=Z_{S_3}(x_1,x_2,x_3)=\dfrac{1}{6}[x_1^3+3x_1x_2+2x_3],
$$
а количество непомеченных графов на трех вершинах равно
$$
Z_{\Sigma_{S_3}}(2,2,2)=Z_{S_3}(2,2,2)=\dfrac{1}{6}[2^3+3\cdot 2\cdot 2+2\cdot 2]=4.
$$
Все эти четыре графа показаны на рис \ref{fig:unlabelled_grphs}.


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/unlabelled_graphs.eps}
\caption{Непомеченные графы на трёх вершинах}
\label{fig:unlabelled_grphs}
\end{figure}


\mysubitem Опишем теперь действие группы $S_n$ на множестве $\tilde{X}$ ребер полного графа $K_n$ в случае $n=4$. 

Нейтральный элемент группы $S_4$ оставляет все $\BCf{4}{2}=6$ ребер такого графа на месте. Поэтому цикловой тип образа этого элемента в группе $\Sigma_{S_4}$ перестановок шести ребер графа $K_4$ равен $\{6,0,0,0,0,0\}$ (слагаемое $x_1^6$ в цикловом индексе $Z_{\Sigma_{S_4}}$). 

В группе $S_4$ имеется шесть перестановок $\sigma\in S_4$ 
$$
(12)(3)(4),\qquad (13)(2)(4),\qquad (14)(2)(3),\qquad (23)(1)(4),\qquad (24)(1)(3),\qquad (34)(1)(2),
$$
меняющих местами только две вершины графа. Любая такая перестановка оставляет на месте ребро, соединяющее эту пару вершин, а также ребро, соединяющее оставшуюся пару вершин. Оставшиеся четыре ребра полного графа $K_4$ разбиваются на пары, меняющиеся местами при такой перестановке вершин. Так, например, перестановка $(12)(3)(4)$ оставляет на месте ребра $(12)$ и $(34)$. Ребро $(13)$ под действием этой перестановки переходит в ребро $(23)$, а ребро $(23)$, наоборот, переходит на место ребра $(13)$. Аналогичным образом меняются местами ребра $(14)$ и $(24)$. Как следствие, любая перестановка $\sigma\in S_4$ описанного вида приводит к появлению слагаемого $x_1^2x_2^2$ в цикловом индексе группы $\Sigma_{S_4}$. 

Заметим теперь, что ровно к тому же результату приводят и три перестановки вершин графа $K_4$ вида
$$
(12)(34),\qquad (13)(24),\qquad (14)(23).
$$
Действительно, в случае, например, перестановки $(12)(34)$ на месте по-прежнему остаются ребра $(12)$ и $(34)$, ребра $(13)$, $(24)$ меняются местами друг с другом, и также ведет себя пара ребер $(14)$, $(23)$. Как следствие, всем этим перестановкам отвечают еще три слагаемых вида $x_1^2x_2^2$ в цикловом индексе $Z_{\Sigma_{S_4}}$.

Восемь перестановок 
$$
(1)(234),\quad (1)(243),\quad (2)(134),\quad (2)(143),\quad(3)(124),\quad (3)(142),\quad (4)(123),\quad (4)(132)
$$
вершин графа $K_4$ циклически переставляют как три ребра, соединяющие три вершины заданного цикла, так и три оставшихся ребра $K_4$. Например, в процессе перестановки $(123)(4)$ ребро $(12)$ переходит на место ребра $(23)$, ребро $(23)$ становится на место ребра $(31)$, а ребро $(31)$ --- на место ребра $(12)$. При этом оставшаяся тройка ребер также циклически переходит в себя: $(14)\to(24)\to(34)\to(14)$. Таким образом, действие каждой из описанных выше восьми перестановок приводит к появлению слагаемого $x_3^2$ в цикловом индексе $Z_{\Sigma_{S_4}}$. 

Наконец, шесть перестановок 
$$
(1234),\qquad (1243),\qquad (1342),\qquad (1324),\qquad(1423),\qquad (1432)
$$
вершин $K_4$ циклически переставляют четыре внешних ребра графа $K_4$, а также меняют местами два диагональных ребра. К примеру, действие перестановки $(1234)$ приводит к следующим перестановкам множества $\tilde{X}$ ребер графа $K_4$:
$$
(12)\to(23)\to(34)\to(41)\to(12),\qquad \qquad (13)\to(24)\to(13).
$$
Следовательно, в цикловом индексе $Z_{\Sigma_{S_4}}$ имеется слагаемое $6x_2^1x_4^1$. 

Таким образом, окончательно цикловой индекс группы $\Sigma_{S_4}$ рассчитывается по формуле
$$
Z_{\Sigma_{S_4}}(x_1,x_2,x_3,x_4,x_5,x_6)=\dfrac{1}{24}[x_1^6+9x_1^2x_2^2+8x_3^2+6x_2^1x_4^1].
$$
Подставляя в это выражение $x_i=2$, мы получаем, что количество всех непомеченных графов на четырех вершинах равно
$$
Z_{\Sigma_{S_4}}(2,2,2,2,2,2)=\dfrac{1}{24}[2^6+9\cdot2^2\cdot 2^2+8\cdot 2^2+6\cdot 2^1\cdot 2^1]=11.
$$
Сами же эти графы показаны на рис. \ref{fig:unlabelled_graphs4}.

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/unlabelled_graphs_4.eps}
\caption{Непомеченные графы на четырёх вершинах}
\label{fig:unlabelled_graphs4}
\end{figure}

\mysubitem Аналогичные рассуждения позволяют, в принципе, получить формулу для циклового индекса $Z_{\Sigma_{S_n}}$ и для произвольного значения параметра $n$. Подробности этих рассуждений, равно как и саму формулу для $Z_{\Sigma_{S_n}}$, можно посмотреть, например, в книге \cite{Enum_graphs}.

\section*{Упражнения}

\begin{exerc} \label{ex_cicl_ind_D_4}
Показать, что цикловой индекс группы $D_4$ симметрий квадрата описывается формулой (\ref{cicl_ind_D_4}).
\end{exerc}

\begin{exerc} Записать цикловой индекс группы симметрий куба, действующей на гранях, на вершинах, а также на ребрах куба. С помощью полученных цикловых индексов дать решение задачи о подсчете геометрически различных способов окраски вершин куба в не более чем два цвета и ребер куба в не более чем два цвета.
\end{exerc}

\begin{exerc} Доказать, что в случае простого числа $p$ цикловой индекс циклической группы $C_p$, действующей на множестве $\tilde{X}$ вершин правильного $p$-угольника, рассчитывается по формуле
\begin{equation}
\label{cicl_ind_cicl_p}
Z_{C_p}(x_1,\ldots,x_p)=\dfrac{1}{p}[x_1^p+(p-1)\cdot x_p^1].
\end{equation}
\end{exerc}

\begin{exerc} Доказать, что в случае произвольного натурального числа $n$ цикловой индекс циклической группы $C_n$, действующей на множестве $\tilde{X}$ вершин правильного $n$-угольника, вычисляется по формуле
\begin{equation}
\label{cicl_ind_cicl_n}
Z_{C_n}(x_1,\ldots,x_n)=\dfrac{1}{n}\sum\limits_{d\backslash n}\phi(d)\cdot x_d^{n/d},
\end{equation}
где $\phi(n)$ --- функция Эйлера, описывающая количество целых чисел от $0$ до $(n-1)$, взаимно-простых с $n$. 
\end{exerc}

\begin{exerc} Доказать, что в случае произвольного натурального числа $n$ цикловой индекс группы $D_n$ симметрий правильного $n$-угольника определяется по формуле
\begin{equation}
\label{cicl_ind_diedr_n}
Z_{D_n}(x_1,\ldots,x_n)=\dfrac{1}{2n}\sum\limits_{d\backslash n}\phi(d)\cdot x_d^{n/d}+
\left[\begin{array}{ll}
\dfrac{1}{2}x_1x_2^{(n-1)/2},&\qquad n=2k+1,\\[2ex]
\dfrac{1}{4}x_2^{n/2}+\dfrac{1}{4}x_1^2x_2^{n/2-1},&\qquad n=2k.
\end{array}\right.
\end{equation}
\end{exerc}

\section*{Решение упражнений}

\begin{sol_exerc}
Действительно, тождественная перестановка дает слагаемое $x_1^4$ в (\ref{cicl_ind_D_4}). Повороты на $90^{\circ}$ и $270^{\circ}$ циклически переставляют все четыре вершины квадрата (слагаемое $2x_4$). Поворот на $180^{\circ}$, а также два вращения относительно осей, проходящих через середины противоположных сторон квадрата, меняют местами две пары вершин квадрата, что дает слагаемое $3x_2^2$  в (\ref{cicl_ind_D_4}). Наконец, вращения относительно осей, проходящих через противоположные вершины квадрата, оставляет эту пару вершин на месте, меняя местами две оставшиеся вершины. Этим двум действиям отвечает слагаемое $2x_1^2x_2$ в (\ref{cicl_ind_D_4}).
\end{sol_exerc}

\begin{sol_exerc}
Как мы показали в упражнении \ref{gr_sim_cube}, в группу симметрий куба входит нейтральный элемент, по три вращения на $90^{\circ}$, $180^{\circ}$ и $270^{\circ}$ относительно осей, проходящих через центры противоположных граней куба, по четыре вращения на $120^{\circ}$ и $240^{\circ}$ вокруг осей, проходящих через противоположные вершины куба, и, наконец, шесть вращений на $180^{\circ}$ относительно осей, проходящих через центры противоположных ребер куба.

Действие этой группы на множестве $\tilde{X}_1$ граней куба описывается следующим цикловым индексом:
$$
Z_1(x_1,x_2,x_3,x_4)=\dfrac{1}{24}[x_1^6+6x_1^2x_4+3x_1^2x_2^2+8x_3^2+6x_2^3].
$$
Действительно, слагаемое $x_1^2x_4$, например, означает, что под действием вращения на $90^{\circ}$ относительно оси, проходящей через центры противоположных граней, две грани остаются неподвижными, а четыре грани циклически переходят друг в друга. В случае поворота на $180^{\circ}$ относительно той же оси две грани по-прежнему остаются неподвижными, а две оставшиеся пары граней меняются местами (слагаемое $x_1^2x_2^2$). При вращении относительно оси, проходящей через пары противоположных вершин куба, две тройки смежных с данной вершиной граней циклически переходят друг в друга (слагаемое $x_3^2$). Наконец, при вращении вокруг оси, проходящей через центры противоположных ребер, три пары граней переходят друг в друга (слагаемое $x_2^3$). 

В случае действия $G$ на множестве $\tilde{X}_2$ вершин куба цикловой индекс записывается в виде 
$$
Z_2(x_1,x_2,x_3,x_4)=\dfrac{1}{24}[x_1^8+6x_4^2+3x_2^4+8x_1^2x_3^2+6x_2^4].
$$
Действительно, мощность множества $\tilde{X}_2$ равна восьми, поэтому действию нейтрального элемента группы $G$ отвечает слагаемое $x_1^8$. При вращении вокруг оси, проходящей через центр противоположных граней куба, на $90^{\circ}$ или на $270^{\circ}$ все вершины меняют свое положение. При этом четверка вершин, принадлежащих верхней грани, переходит циклически в себя, и четверка вершин, принадлежащих нижней грани, также переходит циклически в себя. Так как имеется шесть таких вращений, то в цикловом индексе появляется слагаемое $6x_4^2$. При вращении на $180^{\circ}$ относительно тех же осей пары вершин, принадлежащих как верхней, так и нижней граням, переходят друг в друга. Как следствие, в $Z_2$ появляется слагаемое $3x_2^4$. При вращении вокруг оси, проходящей через противоположные вершины куба, одна пара вершин остается неподвижной, а шесть оставшихся вершин разбиваются на две тройки, переходящие друг в друга при вращениях на $120^{\circ}$ и $240^{\circ}$ (слагаемое $8x_1^2x_3^2$). Наконец, при вращениях вокруг осей, проходящих через середины противоположных ребер, четыре пары вершин переходят друг в друга (слагаемое $6x_2^4$). После приведения подобных слагаемых окончательно получаем
$$
Z_2(x_1,x_2,x_3,x_4)=\dfrac{1}{24}[x_1^8+6x_4^2+9x_2^4+8x_1^2x_3^2].
$$

Читателю предлагается самостоятельно показать, что в случае действия $G$ на ребрах куба соответствующий цикловой индекс будет иметь вид
$$
Z_3(x_1,x_2,x_3,x_4)=\dfrac{1}{24}[x_1^{12}+6x_4^3+3x_2^6+8x_3^4+6x_1^2x_2^5].
$$

Как следствие, количество геометрически различных способов окраски вершин куба в не более чем два цвета равно
$$
Z_2(2,2,2,2)=\dfrac{1}{24}[2^8+6\cdot 2^2+9\cdot 2^4+8\cdot 2^2]=23,
$$
а количество геометрически различных способов окраски ребер куба в не более чем два цвета есть
$$
Z_3(2,2,2,2)=\dfrac{1}{24}[2^{12}+6\cdot 2^3+3\cdot 2^6+8\cdot 2^4+6\cdot 2^2\cdot 2^5]=218.
$$
\end{sol_exerc}


\begin{sol_exerc}
Напомним некоторые простейшие факты элементарной теории групп, полезные для этого и следующего упражнений.

\begin{defin} Порядком элемента $g$ группы $G$ называется наименьшее натуральное $n$, такое, что
$$
g^n=e,
$$
где $e$ --- нейтральный элемент группы. 
\end{defin}

\begin{lemm}\label{lemm_por_el}
Пусть $g\in G$ есть элемент группы $G$ $n$-го порядка. Тогда все элементы 
$$
e,g,g^2,\ldots,g^{n-1}
$$
в группе $G$ различны.
\end{lemm}

\evidp Действительно, пусть $g^i=g^j$, и пусть для определенности $0\leq i<j<n$. Тогда $g^{i-j}=e$, что противоречит тому, что $g$ есть элемент $n$-го порядка. \qed 

\begin{conseq}
Пусть $g\in G$ есть элемент $n$-го порядка. Тогда для любого $m\in \Z$ элемент $g^m$ совпадает с одним из элементов $e,g,g^2,\ldots,g^{n-1}$.
\end{conseq}

\evidp Достаточно поделить $m$ на $n$ с остатком и воспользоваться леммой \ref{lemm_por_el}.

\begin{conseq}\label{cons_2_por_el}
Пусть $g\in G$ есть элемент $n$-го порядка. Элемент $g^m=e$ тогда и только тогда, когда $n\backslash m$.
\end{conseq}

\evidp Деление $m$ на $n$ с остатком дает $g^{kn+l}=g^l=e$, откуда следует согласно лемме \ref{lemm_por_el}, что $l=0$.

\begin{defin}
Пусть $g$ есть элемент $n$-го порядка, и кроме элементов $e,g,g^2,\ldots,g^{n-1}$ в группе $G$ нет других элементов. Тогда $G$ называется циклической группой $C_n$ порядка $n$, порожденной элементом $g\in C_n$, а сам элемент $g$  называется порождающим элементом этой группы.
\end{defin}

Рассмотрим теперь самый простой случай группы $C_n$, случай, когда $n=p$ --- простому числу. 

\begin{lemm}
Любой элемент группы $C_p$, отличный от $e$, имеет порядок, равный $p$, то есть является образующим элементом группы $C_p$. 
\end{lemm}

\evidp По определению циклической группы, в $C_p$ существует элемент $g$ порядка $p$, и все элементы группы $C_p$ имеют вид $e,g,g^2,\ldots,g^{p-1}$. В случае $p=2$ утверждение очевидно, поэтому далее считаем, что $p>2$. Рассмотрим для любого $1<m<p$ элемент $g^m$ и возведем его в степень $p$:
$$
(g^m)^p=g^{mp}=(g^p)^m=e^m=e.
$$
Согласно следствию \ref{cons_2_por_el} из леммы \ref{lemm_por_el}, последнее равенство означает, что порядок элемента $g^m$ делит $p$. Но $p$ --- простое число, поэтому порядок элемента $g^m$ либо равен единице, либо $p$. Однако первый вариант невозможен: $g^m\neq e$ по лемме \ref{lemm_por_el}. Следовательно, порядок элемента $g^m$ равен $p$ для любого $m=1,2,\ldots,(p-1)$. \qed

Перейдем теперь к вычислению циклового индекса группы $C_p$, а точнее, образа $\Sigma_p$ этой группы при гомоморфизме $\phi:\,C_p\to\,S_p$. В группе $C_p$ имеется нейтральный элемент, а также $(p-1)$ элементов, имеющих порядок $p$. Как следствие, образ $\Sigma_p$ этой группы при гомоморфизме $\phi$ состоит из тождественной перестановки (слагаемое $x_1^p$ в формуле (\ref{cicl_ind_cicl_p})), а также из $(p-1)$-й перестановки, каждая из которой представляет собой цикл длины $p$ (слагаемое $(p-1)\cdot a_p^1$ в формуле (\ref{cicl_ind_cicl_p})).  

\end{sol_exerc}

\begin{sol_exerc}
Для вывода формулы (\ref{cicl_ind_cicl_n}) нам понадобится следующее утверждение.

\begin{theor}
Пусть элемент $g$ циклической группы $C_n$ имеет порядок $n$. Тогда порядок элемента $g^k$ равен
$$
\dfrac{n}{\gcd(n,k)}=:\dfrac{n}{d},
$$
где $d$ --- наибольший общий делитель чисел $n$ и $k$. Кроме того, этот элемент $g^k$ образует в $C_n$ подгруппу
$$
H=\{e,g^k,g^{2k},\ldots,g^{(n/d-1)k}\}
$$
порядка $n_1:=n/d$. 
\end{theor}

\evidp Пусть $n=n_1\cdot d$, $k=k_1\cdot d$, причем $\gcd(n_1,k_1)=1$. Рассмотрим натуральное число $m$, такое, что
$$
(g^k)^m=e\qquad \Longleftrightarrow \qquad g^{km}=e.
$$
Согласно следствию \ref{cons_2_por_el}, последнее равенство означает, что порядок $n$ элемента $g$ делит $km$, то есть $n_1$ делит $k_1m$. Но так как числа $k_1$ и $n_1$ взаимно-простые, то отсюда следует, что $n_1$ делит $m$. Последнее же, согласно тому же следствию \ref{cons_2_por_el}, означает, что в таком случае $n_1=n/d$ есть порядок элемента $g^k$. То, что $H$ является при этом циклической подгруппой порядка $n_1=n/d$, следует из определения порядка элемента группы. \qed

\begin{conseq} \label{por_el_n} Все элементы $g^k$, для которых $\gcd(n,k)=1$, являются порождающими элементами группы. Количество таких элементов равно $\phi(n)$, то есть описывается функцией Эйлера. 
\end{conseq}

\begin{conseq} \label{por_el_n_1} Количество элементов $g^k$, имеющих порядок, равный $n_1=n/d$, равно $\phi(n_1)$. 
\end{conseq}

Для доказательства этого факта достаточно рассмотреть подгруппу $H$, порожденную элементом $g^k$, и сослаться на следствие \ref{por_el_n}. 

Теперь перейдем к вычислению циклового индекса $Z_{\Sigma_{C_n}}$ образа группы $C_n$ при гомоморфизме этой группы в симметрическую группу $S_n$. Следствие \ref{por_el_n} говорит нам о том, что в $\Sigma_{C_n}$  имеется ровно $\phi(n)$ перестановок, имеющих длину $n$. Всем этим перестановкам отвечает слагаемое $\phi(n)\cdot a_n^1$ в формуле (\ref{cicl_ind_cicl_n}). Далее, нейтральному элементу группы $C_n$ отвечает, как обычно, слагаемое $a_1^n$ в этой формуле. Наконец, для любого делителя $n_1$ числа $n$, согласно следствию \ref{por_el_n_1}, в группе $\Sigma_{C_n}$ имеется $\phi(n_1)$ перестановок, раскладывающихся в произведение $d=n/n_1$ циклов длины $n_1$. Всем таким перестановкам соответствуют слагаемые вида $x_{n_1}^{d_1}$ в формуле (\ref{cicl_ind_cicl_n}).

Рассмотрим в качестве примера цикловой индекс $Z_{\Sigma_{C_6}}$. В группе $C_6$ имеются два элемента $g_1$ и $g_5$ порядка $6$, соответствующие повороту на углы $\pi/6$ и $-\pi/6$ соответственно. Этим элементам отвечает слагаемое $\phi(6)\cdot x_6^1=2\cdot x_6^1$ в цикловом индексе $Z_{\Sigma_{C_6}}$. Элементы $g_2$ и $g_4$, представляющие собой повороты на углы $\pi/3$ и $2\pi/3$ соответственно, вместе с нейтральным элементом группы образуют подгруппу $H$ группы $C_6$ порядка $3$. Образы элементов $g_2$ и $g_4$ представляют собой перестановки, цикловой тип которых равен $\{0,0,1,0,0,0\}$, поэтому этим перестановкам в  $Z_{\Sigma_{C_6}}$ отвечает слагаемое $\phi(3)\cdot x_3^2=2\cdot x_3^2$. Наконец, образ элемента $g_3$ --- поворота на угол $\pi$ --- представляет собой перестановку с цикловым типом  $\{0,1,0,0,0,0\}$. Ей в цикловом индексе соответствует слагаемое $\phi(2)\cdot x_2^3=1\cdot x_2^3$. Следовательно,
$$
Z_{C_6}(x_1,\ldots,x_6)=\dfrac{1}{6}[x_1^6+x_2^3+2\cdot x_3^2+2\cdot x_6^1]. 
$$

\end{sol_exerc}


\begin{sol_exerc}

Действительно, в случае нечетного $n$ для любой вершины многоугольника существует вращение вокруг оси, проходящей через эту вершину и центр противоположной грани. При таком вращение сама эта вершина остается неподвижной, а остальные $(n-1)$ вершин попарно меняются местами. Как следствие, по сравнению с цикловым индексом $Z_{C_n}$ в $Z_{D_n}$ добавляются $n$ слагаемых вида $x_1x_2^{(n-1)/2}$. 

В случае четного $n$ существуют $n/2$ вращений относительно осей, проходящих через центры противоположных граней многоугольника (слагаемые $x_2^{n/2}$ в формуле (\ref{cicl_ind_diedr_n})), а также $n/2$ вращений относительно осей, проходящих через пары противоположных вершин многогранника (слагаемые вида $x_1^2x_2^{n/2-1}$ в (\ref{cicl_ind_diedr_n})).

\end{sol_exerc} 




\section{Теория перечисления Пойа}

\myitem В предыдущем параграфе мы показали, как, зная цикловой индекс группы $\Sigma_G$ перестановок элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$, определить количество геометрически различных способов окраски этих элементов в не более чем $k$ цветов. Заметим, однако, что часто нам хочется получить более подробную информацию о перечисляемых нами объектах. 

\mysubitem Рассмотрим, например, задачу о раскраске вершин квадрата в не более чем два цвета. Мы знаем, что всего существует шесть геометрически различных способов такой раскраски (см.рис.\ref{fig:square_blocks}). Однако, как видно из рисунка, все это множество раскрашенных объектов естественным образом разбивается на пять блоков в зависимости от того, сколько вершин квадрата окрашено в белый цвет. 


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_blocks.eps}
\caption{Раскраски квадрата}
\label{fig:square_blocks}
\end{figure}


Аналогично, в задаче о перечислении графов на $n$ вершинах все множество таких графов естественным образом разбивается на блоки в зависимости от того, сколько ребер имеет тот или иной граф (рис.\ref{fig:graphs_blocks}). 

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/unlabelled_graphs_4_blocks.eps}
\caption{Непомеченные графы на четырёх вершинах}
\label{fig:graphs_blocks}
\end{figure}

\mysubitem Напомним, что ранее мы уже научились разбивать произвольное множество $X$ на блоки $X_k$, рассматривая отображение
$$
w\,:\,X\,\longrightarrow\,K
$$
множества $X$ в некоторое коммутативное кольцо $K$, при котором всем элементам $x$ данного
блока $X_k$ сопоставляется одно и то же значение $w(x)=k$ (один и тот же вес $k$):
$$
X=\bigcup\limits_{k\in K}X_k,\qquad X_k:=\{x\,\,|\,\,w(x)=k\}.
$$
Самому множеству $X$ при таком подходе мы в кольце $K$ сопоставляли элемент
$$
\phi\equiv w(X):=\sum\limits_{x\in X}w(x)=\sum\limits_{k\in K}c_k\cdot k,\qquad \qquad c_k=|w^{-1}(k)|,
$$
называемый энумератором множества $X$. В частном случае отображения $w$ вида
$$
w:X\longrightarrow \C[[z]],
$$
сопоставляющего любому элементу $x\in X$ формальный степенной ряд
$$
w(x)=0\cdot 1+0\cdot z+\ldots+0\cdot z^{k-1}+1\cdot z^k+0\cdot z^{k+1}+\ldots=z^k,
$$
мы получали в $\C[[z]]$ обыкновенную производящую функцию 
$$
\phi(z):=\sum\limits_{x\in X}w(x)=\sum\limits_{n=0}^{+\infty}c_nz^n,
$$
коэффициенты $c_n$ которой определяют количество элементов множества $X$, имеющих заданный вес $z^n$. 

\mysubitem С учетом вышесказанного вполне удовлетворительным способом подробного описания количества различных способов окраски вершин квадрата является построение производящей функции вида
$$
\phi(z):=1+z+2z^2+z^3+z^4,
$$
коэффициенты при $z^i$ в которой дают нам количество геометрически различных способов окраски, при которых ровно $i$ из $n$ вершин окрашены в белый цвет. Общее же количество способов окраски при таком подходе получается подстановкой значения $z=1$ в выражение для $\phi(z)$. 

Еще один способ описания разбиения множества всех раскрасок вершин квадрата на блоки состоит в построении энумератора этого множества вида
$$
\phi(b,w)=b^4+wb^3+2w^2b^2+w^3b+w^4,
$$
коэффициенты при $w^ib^{n-i}$ которого описывают количество геометрически различных способов окраски вершин квадрата, при которых $i$ вершин окрашено в белый, а $(n-i)$ вершин --- в черный цвет.

Основная задача данного параграфа --- дать конструктивный способ построения такого рода энумераторов для общей задачи окраски элементов геометрической фигуры $\Gamma$ в не более чем $k$ цветов.  


\myitem Начнем мы с несколько более простой задачи --- с построения энумератора $W$ множества $X$ различных способов окраски помеченных элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$ в не более чем $k$ цветов. 

\mysubitem Напомним еще раз формальную постановку задачи. Пусть $\tilde{X}$ есть $n$-множество элементов некоторой фигуры $\Gamma$, а $Y$ есть $k$-множество цветов. Тогда любой элемент  $f:\tilde{X}\to Y$ множества $X\equiv Y^{\tilde{X}}$ всех отображений $\tilde{X}$ в $Y$ задает нам некоторый способ окраски помеченных элементов фигуры $\Gamma$. Нам хочется каким-то разумным способом ввести энумератор множества $Y^{\tilde{X}}$ всех таких отображений. Оказывается, что сделать это можно в два этапа. 

\mysubitem На первом этапе мы построим энумератор множества $Y$ цветов. Для этого, напомним, нам следует ввести отображение $w\,:\,Y\,\longrightarrow\,K$ множества $Y$ в некоторое коммутативное кольцо $K$, сопоставляющее любому элементу $y\in Y$ его вес $w(y)\in K$. Суммируя все такие веса, мы получаем энумератор
\begin{equation}
\label{enum_Y_total}
\phi\equiv w(Y)=\sum\limits_{y\in Y}w(y)=\sum\limits_{k\in K}c_k\cdot k
\end{equation} 
множества $Y$. 

Например, в задаче о раскраске вершин квадрата мы можем рассмотреть отображение 
$$
w\,:\,Y=\{y_1,y_2\}\,\longrightarrow\,K=\{b,w\},
$$ 
сопоставляющее различным элементам $y_i\in Y$ различные элементы кольца $K$:
\begin{equation}
\label{enum_b_w}
w(y_1)=b,\qquad\qquad w(y_2)=w.
\end{equation}
Такое отображение $w$ дает нам для $Y$ энумератор вида
$$
\phi(b,w)=b+w.
$$

Рассматривая для той же задачи в качестве $K$ кольцо $\C[[z]]$ формальных степенных рядов и полагая
\begin{equation}
\label{enum_1_z}
w(y_1)=z^0=1,\qquad \qquad w(y_2)=z^1=z,
\end{equation}
мы получаем для множества $Y$ цветов обыкновенную производящую функцию вида
$$
\phi(z)=1+z.
$$

\mysubitem Определив вес любого элемента $y\in Y$, мы можем теперь перейти ко второму этапу --- определению веса $W(f)$ произвольной функции $f:\tilde{X}\to Y$, $f\in Y^{\tilde{X}}$. Для этого, следуя подходу, изложенному в работе Николаса де Брейна \cite{de_Bruin}, мы введем вес любого окрашенного элемента $x\in \tilde{X}$ фигуры $\Gamma$ как $w(f(x))$ и положим  \emph{по определению}
\begin{equation}
\label{enum_set_of_maps}
W(f):=\prod\limits_{x\in\tilde{X}}w(f(x))\qquad \qquad \forall\,\,f\in Y^{\tilde{X}}.
\end{equation}
Иными словами, вес любой фигуры $\Gamma$, элементы $x\in \tilde{X}$ которой окрашены в цвета из множества $Y$, равен произведению весов всех окрашенных элементов этой фигуры. 

Покажем, что это определение корректно. Действительно, образ $f(x)$ любого элемента $x\in \tilde{X}$ при отображении $f:\tilde{X}\to Y$ представляет собой некоторый элемент $y$ множества $Y$ цветов, для которого корректно определен вес $w(y)=w(f(x))\in K$. Так как элементы кольца мы можем не только складывать, но и перемножать друг с другом, то произведение всех таких образов для фиксированного отображения $f$ представляет собой некоторый элемент кольца $K$. Следовательно, правило (\ref{enum_set_of_maps}) корректно задает некоторое отображение $W$ множества $X$ всех функций $f:\tilde{X}\to Y$ в кольцо $K$. 

В качестве примера вновь рассмотрим задачу о раскраске вершин квадрата в не более чем два цвета. Предположим, что на множестве $Y$ введен описанный в предыдущем пункте энумератор $\phi(b,w)=b+w$, соответствующий отображению (\ref{enum_b_w}). Квадрату, все вершины которого окрашены в черный цвет, отвечает функция $f_1:\tilde{X}\to Y$ вида
$$
f_1(x_1)=f_1(x_2)=f_1(x_3)=f_1(x_4)=y_1.
$$
Так как вес элемента $y_1$ равен $w(y_1)=b$, то, согласно формуле (\ref{enum_set_of_maps}), вес функции $f_1$ равен
$$
W(f_1)=\prod\limits_{i=1}^4 w(f_1(x_i))=\prod\limits_{i=1}^4 w(y_1)=b^4.
$$
Квадрату, у которого вершина $1$ окрашена в белый цвет, а остальные три вершины --- в черный цвет, соответствует функция
$$
f_2\in Y^{\tilde{X}}:\qquad\qquad f_2(x_1)=y_2,\qquad f_2(x_2)=f_2(x_3)=f_2(x_4)=y_1.
$$
Так как $w(y_2)=w$, а $w(y_1)=b$, то вес этой функции равен
$$
W(f_2)=\prod\limits_{i=1}^4 w(f_1(x_i))=w\cdot b^3.
$$

В случае, когда энумератор множества $Y$ задан равенствами (\ref{enum_1_z}), веса описанных выше функций $f_1$ и $f_2$, очевидно, равны
$$
W(f_1)=1,\qquad\qquad W(f_2)=z.
$$

\mysubitem Определив вес каждой функции $f:\tilde{X}\to Y$, мы легко можем построить энумератор всего множества $X=Y^{\tilde{X}}$. Действительно, по определению, энумератор любого множества есть сумма весов всех его элементов. Суммируя $W(f)$ по всем возможным функциям $f$, мы получаем для $Y^{\tilde{X}}$ энумератор вида
$$
\Phi\equiv W(Y^{\tilde{X}})=\sum\limits_{f\in Y^{\tilde{X}}} W(f).
$$

Так, в задаче о раскраске вершин квадрата в случае, когда энумератор множества $Y$ цветов задан формулами (\ref{enum_b_w}), соответствующий ему энумератор множества $Y^{\tilde{X}}$ всех отображений $f:Y\to \tilde{X}$ имеет вид
$$
\Phi(b,w)=b^4+4b^3w+6b^2w^2+4bw^3+w^4,
$$
а в случае, когда в качестве энумератора $Y$ выступает обыкновенная производящая функция $\phi(z)=1+z$, соответствующий ей энумератор множества $Y^{\tilde{X}}$ представляет собой обыкновенную производящую функцию вида
$$
\Phi(z)=1+4z^3+6z^2+4z+1.
$$

\mysubitem Заметим теперь, что в обоих примерах энумераторы множества $X$ можно свернуть, записав их в виде
$$
\Phi(b,w)=(b+w)^4=[\phi(b,w)]^4 \qquad \text{и} \qquad \Phi(z)=(1+z)^4=[\phi(z)]^4. 
$$
Учитывая, что степень $4$ в этой задаче есть мощность множества $\tilde{X}$, мы приходим к предположению о том, что и в общем случае энумератор $W(X)$ множества $X=Y^{\tilde{X}}$ выражается через энумератор $W(Y)$ множества $Y$ по формуле
\begin{equation}
\label{enum_X_from_Y}
W(Y^{\tilde{X}})=[W(Y)]^{|\tilde{X}|}.
\end{equation}
Оказывается, это предположение верно. Именно, справедлива

\begin{theor} Пусть $W(Y)$ есть некоторый энумератор множества $Y$ цветов, и пусть вес $W(f)$ произвольной функции $f:\tilde{X}\to Y$, описывающей некоторую раскраску элементов множества $\tilde{X}$ в цвета из множества $Y$, рассчитывается по формуле (\ref{enum_set_of_maps}). Тогда энумератор $W(Y^{\tilde{X}})$ множества $Y^{\tilde{X}}$ всех функций $f$ выражается через энумератор $W(Y)$ множества $Y$ цветов по формуле (\ref{enum_X_from_Y}). 
\end{theor}

\evidp Распишем правую часть равенства (\ref{enum_X_from_Y}) в следующем виде:
\begin{equation}
\label{n_brackets}
[W(Y)]^{|\tilde{X}|}=\underbrace{[w(y_1)+\ldots+w(y_k)]\cdot[w(y_1)+\ldots+w(y_k)]\cdot\ldots\cdot 
[w(y_1)+\ldots+w(y_k)]}_{\mbox{$n$ сомножителей}}.
\end{equation}
При перемножении этих $n$ скобок мы получаем $k^n$ слагаемых. Заметим теперь, что это количество совпадает с числом всевозможных функций $f:\tilde{X}\to Y$. Этот факт позволяет нам установить взаимно-однозначное соответствие между $k^n$ слагаемыми, получаемыми при перемножении $n$ скобок в правой части (\ref{n_brackets}), и всеми функциями $f$, описывающими различные способы окраски элементов множества $\tilde{X}$ в цвета из множества $Y$. 

Сделать это можно, например, следующим образом. Сопоставим первой скобке в правой части (\ref{n_brackets}) элемент $x_1\in\tilde{X}$, второй скобке --- элемент $x_2\in\tilde{X}$, и так далее. Иными словами, будем считать, что все элементы $y_i$ в первой скобке есть образы элемента $x_1\in\tilde{X}$, все элементы $y_i$ во второй скобке есть образы элемента $x_2\in\tilde{X}$, и так далее. В этом случае, выбирая какое-то слагаемое $w(y_i)$ из первой скобки, какое-то слагаемое $w(y_j)$ из второй скобки и так далее, мы тем самым задаем некоторую функцию $f:\tilde{X}\to Y$, которая на элементе $x_1$ принимает значение $f(x_1)=y_i$, на элементе $x_2$ принимает значение $f(x_2)=y_2$ и так далее. Причем этой функции $f$ в результате перемножения скобок в правой части (\ref{n_brackets}) отвечает выражение вида
$$
\prod\limits_{x\in\tilde{X}}w(f(x)),
$$
то есть, по определению, вес $W(f)$ этой функции. 

Всего в результате перемножения скобок получаем $k^n$ таких слагаемых, каждое из которых описывает вес $W(f)$ одной из $k^n$ функций $f:\tilde{X}\to Y$. Следовательно, стоящее в правой части (\ref{n_brackets}) выражение равно
$$
\sum\limits_{f\in Y^{\tilde{X}}}W(f),
$$
то есть, по определению, представляет собой энумератор множества $Y^{\tilde{X}}$. \qed


\myitem Теперь предположим, что на множестве $\tilde{X}$ элементов геометрической фигуры $\Gamma$ действует группа $G$, то есть задан бинарный оператор $\circ:G\times \tilde{X}\to \tilde{X}$. Это действие, как мы знаем, индуцирует действие $\bullet$ на множестве $Y^{\tilde{X}}$ всех функций $f:\tilde{X}\to Y$ по формуле
$$
(g\bullet f)(x):=f(g^{-1}\circ x).
$$
Действие $\bullet$ вводит на множестве всех функций отношение эквивалентности, разбивающее все множество $Y^{\tilde{X}}$ на классы эквивалентности --- орбиты элементов $Y^{\tilde{X}}$ под действием группы $G$. Наша задача --- построить энумератор $W(Y^{\tilde{X}}/G)$ этого множества $Y^{\tilde{X}}/G$ орбит. 

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_orbit.eps}
\caption{Раскраски из одной орбиты имеют равные веса}
\label{fig:square_orbit}
\end{figure}

\mysubitem Начать нужно, конечно же, с определения веса произвольной орбиты $F\in Y^{\tilde{X}}/G$. Интуитивно ясно, что веса элементов $f$ любой орбиты $F$ должны совпадать. Действительно, рассмотрим, к примеру, четыре способа окраски помеченных вершин квадрата в не более чем два цвета, показанные на рис. \ref{fig:square_orbit}. Все они переходят друг в друга под действием группы $G=D_4$ симметрии квадрата. Как следствие, количество вершин, окрашенных в данный конкретный цвет (например, в белый), у этих квадратов одинаков. Поэтому и вес каждого из этих квадратов одинаков и равен $w^2b^2$. Ясно, что этот факт должен оставаться верным и в общем случае. 

Именно, справедливо следующее несложное

\begin{propos} \label{equiv_funct}
Пусть $W(Y)$ есть некоторый энумератор множества $Y$ цветов, и пусть вес $W(f)$ произвольной функции $f:\tilde{X}\to Y$, описывающей некоторую раскраску элементов множества $\tilde{X}$ в цвета из множества $Y$, рассчитывается по формуле (\ref{enum_set_of_maps}). В этом случае все функции $f$, принадлежащие одной и той же орбите $F\in Y^{\tilde{X}}/G$ элементов множества $Y^{\tilde{X}}$ под действием группы $G$, имеют один и тот же вес.
\end{propos}

\evidp Напомним, что пара функций $f_1,f_2$ принадлежит одной и той же орбите $F$, если существует элемент $g\in G$, такой, что 
$$
f_1(x)=f_2(g^{-1}\circ x)\qquad\qquad \forall \,\,x\in X.
$$

Рассмотрим теперь следующую цепочку равенств:
$$
W(f_1):=\prod\limits_{x\in\tilde{X}}w(f_1(x))=\prod\limits_{x\in\tilde{X}}w(f_2(g^{-1}\circ x))=\prod\limits_{x\in\tilde{X}}w(f_2(x)).
$$
Последнее равенство в этой цепочке выполняется потому, что левое и правое произведения имеют одни и те же сомножители, разве что расположенные в разном порядке. Так как кольцо $K$ у нас коммутативно, то порядок следования сомножителей в нем роли не играет, и поэтому левое и правое произведения действительно равны друг другу. Но правое произведение есть, по определению, вес $W(f_2)$ функции $f_2$, поэтому из условия $f_1,f_2\in F$ действительно следует равенство $W(f_1)=W(f_2)$. \qed


\mysubitem Пользуясь утверждением \ref{equiv_funct}, мы можем, наконец, дать формальное определение энумератора $W(Y^{\tilde{X}}/G)$ множества $Y^{\tilde{X}}/G$ всех орбит. Действительно, возьмем \emph{по определению} в качестве веса орбиты $F\in Y^{\tilde{X}}/G$ вес $W(f)$ любого элемента этой орбиты:
$$
W(F)=W(f)\qquad \qquad \forall\,\,f\in F.
$$
Это определение корректно, так как, в силу утверждения \ref{equiv_funct}, этот вес не зависит от выбора конкретного представителя $f$ элементов орбиты $F$. Суммируя теперь эти веса $W(F)$ по всем возможным орбитам, мы и получаем энумератор $W(Y^{\tilde{X}}/G)$ множества $Y^{\tilde{X}}/G$ всех орбит:
$$
W(Y^{\tilde{X}}/G)=\sum\limits_{F\in Y^{\tilde{X}}/G}W(F).
$$


\mysubitem Итак, мы показали, что функции, принадлежащие одной и той же орбите $F$, имеют одинаковые веса. Обратное, к сожалению, не верно --- существуют функции $f_1,f_2$, принадлежащие разным орбитам и имеющие одни и те же веса.


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_two_orbits.eps}
\caption{Две раскраски одного веса из разных орбит}
\label{fig:square_two_orbits}
\end{figure}

Рассмотрим в качестве примера задачу о раскраске вершин квадрата в не более чем два цвета. Пусть функция $f_1$ описывает раскраску вершин, при которой две пары противоположных вершин окрашены в разный цвет, а функция $f_2$ отвечает раскраске, при которой в разный цвет окрашены две пары соседних вершин (рис.\ref{fig:square_two_orbits}). Очевидно, что эти функции принадлежат различным орбитам множества $Y^{\tilde{X}}$ под действием группы $D_4$ симметрий квадрата --- никакой элемент $g$ группы $D_4$ не может перевести одну такую раскраску в другую. Однако обе эти раскраски имеют одинаковый вес. Так, в случае, когда на множестве $Y$ введен энумератор $\phi(b,w)=b+w$, описывающийся отображениями (\ref{enum_b_w}), веса $W(f_1)=W(f_2)=b^2w^2$. В случае, когда энумератор множества $Y$ есть обыкновенная производящая функция вида $\phi(z)=1+z$, эти веса равны $W(f_1)=W(f_2)=z^2$. 

Нам, таким образом, нужно уметь считать количество орбит, имеющих один и тот же вес. В принципе, это можно сделать, используя всю ту же лемму Бернсайда.


\mysubitem Действительно, пусть $Z\subset X$ есть некоторое подмножество множества $X$, замкнутое относительно действия группы $G$. Иными словами, действие группы $G$ не выводит нас за пределы данного подмножества $Z$. Тогда непосредственным следствием леммы Бернсайда (или просто ее переформулировкой в терминах множества $Z$) является следующая

\begin{lemm} Количество орбит элементов $Z$ под действием группы $G$ рассчитывается по формуле
$$
|Z/G|=\dfrac{1}{|G|} \sum\limits_{g\in G}|Z^g|.
$$
\end{lemm}

Возьмем теперь в качестве $Z$ подмножество функций $f$, имеющих один и тот же вес. Согласно утверждению \ref{equiv_funct}, если функция $f_1$ имеет какой-то вес $W(f)$, то и любая функция вида $f_2=g\bullet f_1$ также будет иметь тот же самый вес $W(f)$. Следовательно, подмножество $Z$ является замкнутым относительно действия $\bullet$ группы $G$ на $Z$, и к нему применима лемма Бернсайда. 

Однако оказывается, что как и в случае энумератора $W(Y^{\tilde{X}})$, наиболее простой ответ получается, если сосчитать сразу весь энумератор $W(Y^{\tilde{X}}/G)$, а не отдельные его части. Именно, справедлива следующая 

\begin{theor}[Пойа, 1937] \label{Theor_Polya_statement}
Энумератор $W(Y^{\tilde{X}}/G)$ множества орбит элементов $Y^{\tilde{X}}$ под действием группы $G$ рассчитывается по формуле
\begin{equation}
\label{Theor_Polya_formula}
W(Y^{\tilde{X}}/G)=Z_{\Sigma_G}\biggl(\,\sum\limits_{y\in Y}w(y),\sum\limits_{y\in Y}w^2(y),\ldots,
\sum\limits_{y\in Y}w^n(y)\biggr),
\end{equation}
где $Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)$ --- цикловой индекс группы $\Sigma_G$ перестановок множества $\tilde{X}$, $w(y)$ --- вес элемента $y\in Y$. 
\end{theor}

\mysubitem Приступим к доказательству теоремы Пойа. Пусть $\{\omega_1,\ldots,\omega_m\}$ есть множество всех \emph{различных} значений весов функций $f\in Y^{\tilde{X}}$. Например, в задаче о раскраске вершин квадрата в случае, когда энумератор множества $Y$ цветов описывается отображениями (\ref{enum_b_w}), это множество состоит из следующих пяти элементов:
$$
\omega_1=b^4,\qquad \omega_2=wb^3,\qquad \omega_3=w^2b^2,\qquad \omega_4=w^3b,\qquad \omega_5=w^4.
$$ 
Тогда, по определению энумератора, 
$$
W(Y^{\tilde{X}}/G)=\sum\limits_{F\in Y^{\tilde{X}}/G}W(F)=
\sum\limits_{i=1}^m c(\omega_i)\cdot \omega_i,
$$
где $c(\omega_i)$ есть количество орбит $F$, вес $W(F)$ которых равен $\omega_i$. В частности, в нашем примере
$$
W(Y^{\tilde{X}}/G)=b^4+wb^3+2w^2b^2+w^3b+w^4.
$$

Как мы уже упоминали, для любого $i$ количество $c(\omega_i)$ орбит, вес которых равен $\omega_i$, мы можем, вообще говоря, сосчитать с помощью леммы Бернсайда:
$$
c(\omega_i)=\dfrac{1}{|G|}\sum\limits_{g\in G}|X^g_i|.
$$
Здесь $X^g_i$ есть множество функций $f:\tilde{X}\to Y$, имеющих заданный вес $W(f)=\omega_i$ и остающихся неподвижными под действием элемента $g$ (то есть таких, что $g\bullet f=f$). Вместо этого мы подставим выражения для $c(\omega_i)$ в формулу для $W(Y^{\tilde{X}}/G)$ и поменяем в ней порядок суммирования:
$$
W(Y^{\tilde{X}}/G)=\sum\limits_{i=1}^m \omega_i\cdot \dfrac{1}{|G|}\sum\limits_{g\in G}|X^g_i|=
\dfrac{1}{|G|}\sum\limits_{g\in G}\sum\limits_{i=1}^m \omega_i\cdot |X^g_i|.
$$

Заметим теперь, что внутренняя сумма есть просто сумма
\begin{equation}
\label{sum_weights_funct}
\sum\limits_{f:\,g\bullet f=f}W(f)
\end{equation}
весов всех функций, остающихся неподвижными под действием элемента $g\in G$. Действительно, взяв для фиксированного $g\in G$ все функции $f$, для которых $g\bullet f=f$, и просуммировав веса этих функций, мы получим 
$$
\sum\limits_{f:\,g\bullet f=f}W(f)=\omega_1\cdot \{\text{количество функций $f$: $g\bullet f=f$ и $W(f)=\omega_1$}\}+\ldots+
$$
$$
+\omega_m\cdot \{\text{количество функций $f$: $g\bullet f=f$ и $W(f)=\omega_m$}\}=
\sum\limits_{i=1}^m \omega_i\cdot |X^g_i|.
$$
Следовательно, 
$$
W(Y^{\tilde{X}}/G)=\dfrac{1}{|G|}\sum\limits_{g\in G}\,\sum\limits_{f:\,g\bullet f=f}W(f),
$$
и все, что нам осталось --- это сосчитать для любого фиксированного $g\in G$ сумму (\ref{sum_weights_funct}).


\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/square_fixed.eps}
\caption{Неподвижные точки для поворота на $180^{\circ}$}
\label{fig:square_fixed}
\end{figure}

\mysubitem Легче всего понять, как считается такая сумма, на конкретном примере задачи о раскраске вершин квадрата в не более чем два цвета. Рассмотрим элемент $g$ группы $D_4$ симметрий квадрата, отвечающий повороту квадрата на угол $180^{\circ}$. Нас интересуют раскраски вершин квадрата, остающиеся неподвижными под действием элемента $g$. Как мы уже хорошо понимаем, в любой подобной раскраске каждая пара противоположных вершины квадрата должна быть окрашена в один и тот же цвет. Все такие способы окраски показаны на рис. \ref{fig:square_fixed}. Первым двум способам окраски отвечают веса $W(f)=b^2w^2$, а третьему и четвертому --- веса $W(f)=b^4$ и $W(f)=w^4$ соответственно. Суммируя эти веса, получаем, что в данном конкретном случае
$$
\sum\limits_{f:\,g\bullet f=f}W(f)=b^4+2b^2w^2+w^4=(b^2+w^2)^2. 
$$ 
Постараемся теперь понять, почему в данном конкретном случае мы получили такой результат. Повороту на $180$ градусов в группе $\Sigma_G$ отвечает перестановка $\sigma_g=(13)(24)$. Для того, чтобы под действием этой перестановки раскрашенный квадрат перешел в себя, вершины $1$ и $3$ должны быть окрашены \emph{либо} в белый, \emph{либо} в черный цвет. Иными словами, вес этих двух вершин должен быть одинаков и равен либо $b^2$, либо $w^2$. На языке производящих функций выбору одного из двух вариантов отвечает знак плюс. Поэтому окончательно энумератор, описывающий окраску вершин $1$ и $3$, имеет вид $w^2+b^2$. Независимо от выбора цвета вершин $1$ и $3$, вершины $2$ и $4$ также должны быть окрашены либо в первый, либо во второй цвет. Поэтому окраска этих вершин также задается энумератором вида $w^2+b^2$. Окраска же всех четырех вершин, согласно комбинаторному смыслу произведения, описывается энумератором $(b^2+w^2)^2$.

\mysubitem Вернемся теперь к общему случаю и предположим, что соответствующая элементу $g\in G$ перестановка $\sigma_g\in\Sigma_G$ имеет цикловой тип $\{i_1,i_2,\ldots,i_n\}$. Рассмотрим элементы $x\in\tilde{X}$ фигуры $\Gamma$, входящие в один и тот же цикл перестановки $\sigma_g$, имеющий длину $l$. Все эти элементы должны быть окрашены одинаково, то есть должны иметь один и тот же вес. Так как этот вес может быть любым, то энумератор, описывающий нужный нам способ окраски этих вершин, записывается в виде
$$
w^l(y_1)+w^l(y_2)+\ldots+w^l(y_k)=\sum\limits_{j=1}^kw^l(y_j).
$$
При этом энумератор, описывающий все способы окраски, переходящие в себя под действием перестановки $\sigma_g$, равен, очевидно,
$$
\sum\limits_{f:\,g\bullet f=f}W(f)=(w^1(y_1)+\ldots+w^1(y_k))^{i_1}\cdot
(w^2(y_1)+\ldots+w^2(y_k))^{i_2}\cdot \ldots \cdot(w^n(y_1)+\ldots+w^n(y_k))^{i_n}.
$$

Вспоминая теперь, что вся информация о цикловом типе перестановок группы $\Sigma_G$ содержится в цикловом индексе
$$
Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)=
\dfrac{1}{|\Sigma_G|}\sum\limits_{\sigma\in \Sigma_G}x_1^{i_1}x_2^{i_2}\ldots x_n^{i_n}
$$
группы $\Sigma_G$, мы и получаем окончательно формулу (\ref{Theor_Polya_formula}), описывающую энумератор множества непомеченных окрашенных объектов. 

\mysubitem В качестве примера сосчитаем с помощью теоремы Пойа энумератор множества $Y^{\tilde{X}}/D_4$ геометрически различных способов окраски вершин квадрата в не более чем два цвета. Цикловой индекс группы $\Sigma_{D_4}$ перестановок вершин квадрата имеет вид
$$
Z_{\Sigma_{D_4}}(x_1,x_2,x_3,x_4)=\dfrac{1}{8}[x_1^4+2x_1^2x_2+3x_2^2+2x_4].
$$
Подставляя вместо $x_i$ выражения вида $b^i+w^i$, мы и получаем, что
$$
W(Y^{\tilde{X}}/D_4)=\dfrac{1}{8}\left[(b+w)^4+2(b+w)^2(b^2+w^2)+3(b^2+w^2)^2+2(b^4+w^4)\right]=
$$
$$
=b^4+wb^3+2w^2b^2+w^3b+w^4.
$$



\myitem Итак, мы с помощью теории Пойа объяснили, как решать задачи, связанные с раскраской элементов $x\in \tilde{X}$ геометрической фигуры $\Gamma$ в не более чем $k$ цветов, входящих в множество $Y$. Оказывается, с помощью той же теории можно решать и другие задачи подобного рода, например, задачи, связанные с раскраской элементов $x\in\tilde{X}$ ровно в $n$ цветов, $n=|X|$, или задачи, связанные с раскраской этих элементов в $k>n$ цветов так, чтобы ни один из этих цветов в данной раскраске не повторялся, и так далее.

\mysubitem Рассмотрим вначале множество всех взаимно-однозначных функций вида
$$
f:\,\tilde{X}\,\to\,\tilde{Y},\qquad |\tilde{Y}|=n.
$$
Построим для множества $\tilde{Y}$ какой-то энумератор с помощью отображения $w:\tilde{Y}\to K$. Тогда определяемый по формуле (\ref{enum_set_of_maps}) вес любой взаимно-однозначной функции $f$, очевидно, совпадает с весом любой другой такой функции и равен
$$
\tilde{W}(f)=\prod\limits_{y\in\tilde{Y}}w(y).
$$
Как следствие, энумератор всего множества таких функций рассчитывается по формуле
$$
\Phi(\tilde{Y}^{\tilde{X}})=n!\cdot \tilde{W}(f)=n!\cdot \prod\limits_{y\in\tilde{Y}}w(y).
$$

Теперь предположим, что на множестве $\tilde{X}$ действует группа $G$. Как и при доказательстве теоремы Пойа, с использованием леммы Бернсайда несложно доказать, что 
$$
\Phi(\tilde{Y}^{\tilde{X}}/G)=\sum\limits_{F\in \tilde{Y}^{\tilde{X}}/G}W(F)=
\dfrac{1}{|G|}\sum\limits_{g\in G}\sum\limits_{f:\,g\bullet f=f}W(f).
$$
Но все наши функции --- взаимно-однозначные, и переходят в себя только под действием нейтрального элемента $e$ группы $G$. Всего имеется $n!$ таких функций, причем вес этих функций одинаков и равен $\tilde{W}(f)$. Следовательно,
\begin{equation}
\label{biect_funct}
\Phi(\tilde{Y}^{\tilde{X}}/G)=\dfrac{n!}{|G|}\prod\limits_{y\in\tilde{Y}}w(y).
\end{equation}
В частном случае, когда все веса $w(y)=1$, мы получаем знакомый нам из первого параграфа результат: количество способов окраски $n$ предметов в $n$ различных цветов в случае, когда на множестве $\tilde{X}$ предметов действует группа $G$, равен $n!/|G|$.

Особо отметим случай, когда $G=S_n$ --- симметрической группе, действующей на множестве $\tilde{X}$. В этом случае все $n!$ таких функций являются эквивалентными друг другу, то есть принадлежат одной и той же единственной орбите. При этом вес этой единственной орбиты совпадает с весом любого из его представителей и равен
$$
\Phi(\tilde{Y}^{\tilde{X}}/S_n)=\prod\limits_{y\in\tilde{Y}}w(y).
$$

\mysubitem Теперь перейдем к чуть более сложному случаю инъективных функций, то есть таких функций, у которых любой образ имеет не более одного прообраза:
$$
f(x_1)=f(x_2)\qquad \Longrightarrow \qquad x_1=x_2.
$$
Вначале рассмотрим случай, когда на множестве таких функций действует симметрическая группа $S_n$. Покажем, что для этого случая количество орбит на множестве функций $Y^{\tilde{X}}$, $|Y|\geq |X|$, можно подсчитать по формуле
$$
\Phi(Y^{\tilde{X}}/S_n)=Z_{A_n}\biggl(\,\sum\limits_{y\in Y}w(y),\ldots,
\sum\limits_{y\in Y}w^n(y)\biggr)-Z_{S_n}\biggl(\,\sum\limits_{y\in Y}w(y),\ldots,
\sum\limits_{y\in Y}w^n(y)\biggr),
$$
где $A_n$ --- знакопеременная группа порядка $n$. 

Действительно, заметим, прежде всего, что любую инъективную функцию мы можем рассматривать как некоторую взаимно-однозначную функцию, действующую из множества $\tilde{X}$ на множество $f(\tilde{X})=:\tilde{Y}$ всех ее прообразов. Как мы уже знаем, в случае действия на $\tilde{X}$ симметрической группы $S_n$ все функции $f:\tilde{X}\to \tilde{Y}$ эквивалентны между собой, то есть принадлежат одной и той же орбите $F$, а вес этой орбиты равен весу любого из его представителей, то есть
$$
\Phi({\mathbf B}/S_n)=W(F)=\prod\limits_{y\in \tilde{Y}}w(y),
$$
где $\mathbf B$ есть множество всех взаимно-однозначных функций. 
Как видно из формулы (\ref{biect_funct}), в случае действия группы $A_n$ все множество таких функций $f:\tilde{X}\to \tilde{Y}$ разбивается ровно на две орбиты. Действительно, так как порядок $|A_n|$ этой группы равен $n!/2$, то энумератор множества орбит в этом случае равен
$$
\Phi({\mathbf B}/A_n)=2\cdot \prod\limits_{y\in \tilde{Y}}w(y)=2\cdot \Phi({\mathbf B}/S_n).
$$
Заметим, что этот же факт можно доказать и непосредственно. Для этого зафиксируем любую функцию $f_1\in {\mathbf B}$ и поменяем значения этой функции для некоторой произвольно выбранной пары ее аргументов $x_1\neq x_2$. В этом случае мы получим новую взаимно-однозначную функцию
$$
f_2(x)=f_1(\sigma(x))\qquad \forall\,x\in \tilde{X},
$$
где $\sigma\in S_n$ --- это есть перестановка вида $(x_1 \, x_2)$, меняющая местами аргументы $x_1$ и $x_2$. Но так как транспозиция $(x_1 \, x_2)$ не принадлежит группе $A_n$, то эти функции будут лежать в двух различных орбитах $A_n$. Отсюда, собственно, и следует, что все множество взаимно-однозначных функций разбивается под действием $A_n$ ровно на две орбиты. 

Рассмотрим теперь множество ${\mathbf F}$ \emph{всех} функций, действующих из $\tilde{X}$ в $\tilde{Y}$. Все, что нам осталось показать --- это то, что в случае, когда функция $f$ не является взаимно-однозначной, то есть в случае, когда $f\in {\mathbf F}\setminus {\mathbf B}$, количество орбит множества всех таких функций под действием групп $S_n$ и $A_n$ совпадают. Действительно, тогда при вычитании из энумератора $\Phi({\mathbf F}/A_n)$ множества всех функций под действием группы $A_n$ энумератора $\Phi({\mathbf F}/S_n)$ того же множества под действием группы $S_n$ веса орбит, отвечающих неинъективным функциям, сократятся, и мы получим, что
$$
\Phi({\mathbf F}/A_n)-\Phi({\mathbf F}/S_n)=\Phi({\mathbf B}/A_n)-\Phi({\mathbf B}/S_n)=\prod\limits_{y\in \tilde{Y}}w(y).
$$ 

Итак, рассмотрим подмножество функций, у которых значения функций в двух различных точках $x_1$ и $x_2$ совпадают, то есть
$$
f_{\alpha}(x_1)=f_{\beta}(x_2),\qquad\qquad x_1\neq x_2.
$$ 
Для любых двух фиксированных функций такого рода всегда существует некоторая перестановка $\sigma\in S_n$, такая, что 
$$
f_{\alpha}(x)=f_{\beta}(\sigma^{-1}(x))\qquad\qquad \forall\,x\in \tilde{X}.
$$
Если эта перестановка четная, то есть если $\sigma\in A_n$, то функции $f_{\alpha}$ и $f_{\beta}$ принадлежат одной и той же орбите. Если же перестановка $\sigma$ --- нечетная, то четной является перестановка $(x_1\,x_2)\cdot \sigma$, причем
$$
f_{\alpha}(x)=f_{\beta}(((x_1\,x_2)\cdot \sigma)^{-1}(x))\qquad\qquad \forall\,x\in \tilde{X}.
$$
Иными словами, и в этом случае пара функций $f_{\alpha},f_{\beta}$ принадлежит одной и той же орбите множества $F\setminus B$ под действием группы $A_n$. 

Таким образом, нами доказано, что 

\section*{Упражнения}

\begin{exerc} 
Доказать, что количество геометрически различных способов окраски ожерелья в не более чем два цвета, при которых ровно $k$ вершин окрашены в один цвет, определяется по формуле
$$
c_k=\dfrac{1}{n}\sum\limits_{d\backslash \gcd(n,k)}\phi(d)\BCf{n/d}{k/d}.
$$ 
\end{exerc}

\begin{exerc} Показать, что существует ровно один способ окраски непомеченных вершин треугольника в не более чем два цвета, при котором ровно $i$ вершин, $i=0,\ldots,3$, окрашены в белый цвет.
\end{exerc}

\begin{exerc} Пусть на $n$-множестве $\tilde{X}$ действует симметрическая группа $S_n$ всех перестановок элементов множества $\tilde{X}$. Пусть $w:Y\to K$ есть инъективное отображение множества $Y$ в коммутативное кольцо $K$, сопоставляющее любому элементу $y_i\in Y$ вес $w(y_i)=u_i$, $i=1,\ldots,k$, так, что $u_i\neq u_j$, если $i\neq j$.  Такому отображению отвечает энумератор $k$-множества $Y$ цветов вида 
$$
\phi(z)=u_1+u_2+\ldots+u_k.
$$
Наконец, пусть, как обычно, вес $W(f)$ функции $f:\tilde{X}\to Y$, описывающей некоторый способ окраски элементов $x\in \tilde{X}$ в не более чем $k$ цветов, определяется по формуле (\ref{enum_set_of_maps}). Докажите, что обыкновенная производящая функция, описывающая множество $Y^{\tilde X}/S_n$ орбит элементов $f\in Y^{\tilde X}$ под действием группы $S_n$, рассчитывается по формуле
$$
\Phi(u_1,\ldots,u_k)=\sum\limits_{i_1+\ldots+i_k=n}u_1^{i_1}\cdot u_2^{i_2}\cdot \ldots\cdot u_k^{i_k}.
$$
Иными словами, покажите, что, как и в задаче об окраске вершин треугольника в не более чем два цвета, в случае действия на $\tilde{X}$ группы $S_n$ любым двум различным непомеченным элементам (то есть орбитам $F_1,F_2\in Y^{\tilde X}/S_n$: $F_1\neq F_2$) отвечают различные же веса:
$$
W(F_1)\neq W(F_2)\qquad\qquad \Longleftrightarrow \qquad\qquad F_1\neq F_2.
$$ 
\end{exerc}

\section*{Решение упражнений}

\begin{sol_exerc}
В этой задаче на $n$-множестве $\tilde{X}$ вершин действует циклическая группа $C_n$ вращений правильного $n$-угольника. Цикловой индекс соответствующей $C_n$ группы $\Sigma_{C_n}$ перестановок элементов $n$-множества определяется по формуле
$$
Z_{\Sigma_{C_n}}(a_1,\ldots,a_n)=\dfrac{1}{n}\sum\limits_{d\backslash n}\phi(d)\cdot a_d^{n/d}.
$$
Пусть $\phi(z)=1+z$ описывает производящую функцию множества $Y$ цветов. Тогда, согласно теореме Пойа, производящая функция для количества геометрически различных способов окраски ожерелья рассчитывается по формуле
$$
\Phi(z)=\dfrac{1}{n}\sum\limits_{d\backslash n}\phi(d)\cdot (1+z^d)^{n/d}=
\dfrac{1}{n}\sum\limits_{d\backslash n}\phi(d)\sum\limits_{i=0}^{n/d}\BCf{n/d}{i}z^{i\cdot d}.
$$
Введем теперь индекс $k=i\cdot d$. Так как $i$ меняется от $0$ до $n/d$, то $k=0\ldots n$, и
$$
\Phi(z)=\dfrac{1}{n}\sum\limits_{d\backslash n}\phi(d)\sum\limits_{k=0}^n\BCf{n/d}{k/d}z^k=\sum\limits_{k=0}^nc_kz^k,
$$
где 
$$
c_k=\dfrac{1}{n}\sum\limits_{d\backslash n,\,\,d\backslash k}\phi(d)\BCf{n/d}{k/d}=
\dfrac{1}{n}\sum\limits_{d\backslash \gcd(n,k)}\phi(d)\BCf{n/d}{k/d}.
$$

В частности, в случае, когда $n$ и $k$ являются взаимно-простыми, мы получаем, что 
$$
c_k=\dfrac{1}{n}\BCf{n}{k}.
$$

\end{sol_exerc}


\begin{sol_exerc}
Цикловой индекс группы $D_3$ симметрий правильного треугольника равен
$$
Z(a_1,a_2,a_3)=\dfrac{1}{6}[a_1^3+3a_1a_2+2a_3].
$$
Подставляя в эту формулу вместо $a_i$ выражения вида $1+z^i$, получаем обыкновенную производящую функцию
$$
\Phi(z)=\dfrac{1}{6}[(1+z)^3+3(1+z)(1+z^2)+2(1+z^3)]=1+z+z^2+z^3.
$$
\end{sol_exerc}


\begin{sol_exerc}
Мы уже знаем, что если пара функций $f_1,f_2\in Y^{\tilde X}$ принадлежит одной и той же орбите, то эти функции имеют один и тот же вес. Давайте поймем, почему обратное утверждение не всегда выполняется.

Прежде всего, для общего вида отображения $w:Y\to K$ различным элементам $y_i\neq y_j$ может соответствовать один и тот же вес $w(y_i)=w(y_j)=\omega$. В этом случае пара функций $f_1,f_2\in Y^{\tilde{X}}$, таких, что $f_1(x_s)=y_i$, $f_2(x_s)=y_j$ для любых $s=1,\ldots,n$, имеет один и тот же вес $W(f_1)=W(f_2)=\omega^n$. В то же время очевидно, что такая пара функций описывает два геометрически различных способа окраски элементов $x\in \tilde{X}$ цветами из множества $Y$ --- ни один элемент группы $G$ не может перевести фигуру, элементы которой окрашены в один цвет, в фигуру, элементы которой окрашены в другой цвет. В нашей же задаче мы подобный вариант исключили --- разным элементам $y_i\neq y_j$ у нас отвечают различные же веса $u_i\neq u_j$. 

Пусть теперь пара функций $f_1,f_2\in Y^{\tilde{X}}$ имеет один и тот же вес $u_1^{i_1}\cdot u_2^{i_2}\cdot\ldots
\cdot u_k^{i_k},$ $i_1+i_2+\ldots+i_k=n$. В случае инъективного отображения $w:Y\to K$ равенство 
$$
W(f_1)=\prod\limits_{x\in\tilde{X}}w(f_1(x))=u_1^{i_1}\cdot u_2^{i_2}\cdot\ldots
\cdot u_k^{i_k},\qquad i_1+i_2+\ldots+i_k=n
$$
означает, что все множество $\tilde{X}$ разбито на $k$ блоков, имеющих размеры $i_1,\ldots,i_k$, таких, что для элементов первого блока $f_1(x)=y_1$, для элементов второго блока $f_2(x)=y_2$ и так далее. Аналогичное равенство 
$$
W(f_2)=\prod\limits_{x\in\tilde{X}}w(f_2(x))=u_1^{i_1}\cdot u_2^{i_2}\cdot\ldots
\cdot u_k^{i_k},\qquad i_1+i_2+\ldots+i_k=n
$$
говорит нам о том, что $\tilde{X}$ разбито на $k$ блоков тех же самых размеров, что и в предыдущем случае. Каждый блок $l$ состоит теперь, возможно, из другого набора элементов, однако для любого $\hat{x}$ из этого набора по-прежнему выполняется равенство $f_2(\hat{x})=y_l$. 

Заметим теперь, что в группе $S_n$ всегда существует перестановка
$$
\sigma_g=\left(\begin{array}{cccccc}
x_1&x_2&\ldots&x_n\\[2ex]
\hat{x}_1&\hat{x}_2&\ldots&\hat{x}_n
\end{array}\right),
$$
переводящая прообразы $f_1^{-1}(y_l)$ элемента $y_l$, $l=1,\ldots,k$, для отображения $f_1$ в прообразы $f_2^{-1}(y_l)$ того же самого элемента $y_l$, но уже для функции $f_2$. Иными словами, в группе $S_n$ всегда существует перестановка $\sigma_g$, такая, что
$$
(g \bullet f_1)(\hat{x})=f_1(g^{-1}\circ \hat{x})=f_1(\sigma_g^{-1}(\hat{x}))=f_1(x)=y_l=f_2(\hat{x}) \qquad \forall\,\,\hat{x}\in \tilde{X}.
$$ 
Но это означает, в свою очередь, что функции $f_1$ и $f_2$ принадлежат одной и той же орбите под действием группы $S_n$. Следовательно, в случае инъективной функции $w:Y\to K$ и $G=S_n$ любые функции имеют один и тот же вес тогда и только тогда, когда они принадлежат одной и той же орбите. 

\end{sol_exerc}



\section{Действие степенной группы}

\myitem В предыдущих параграфах мы подробно рассмотрели случай, когда на множестве $\tilde{X}$ элементов геометрической фигуры $\Gamma$ действует некоторая группа $G$. Николас де Брейн в работе \cite{deBruijn} обобщил описанные выше результаты на задачи, в которых имеется нетривиальная группа симметрии $H$, действующая и на множестве $Y$ цветов. Достаточно характерный пример такой задачи --- это подсчет количества раскладок $n$ предметов по, например, пяти ящикам, два из которых --- квадратные, а три --- круглые. В этом случае на множестве $Y$ ящиков действует группа $H$, равная декартовому произведению групп $S_2\times S_3$. 

Очевидно, что в случае тривиальной группы $H$ (то есть в случае, когда $H$ состоит из единственного тождественного элемента $id$) мы возвращаемся к ситуации, рассмотренной в предыдущих параграфах. Задача данного параграфа --- обобщить полученные выше результаты на случай действия нетривиальной группы $H$ на множестве $Y$. 

\myitem Итак, пусть на множестве $\tilde{X}$ задано действие $\circ:(G\times X)\to X$ группы $G$ на $\tilde{X}$, а на множестве $Y$ задано действие $*:(H\times Y)\to Y$ группы $H$ на $Y$. Как и в случае действия на $Y$ тривиальной группы, и в этом более общем случае мы можем довольно естественно продолжить действие групп $G$ и $H$ на множество $Y^{\tilde{X}}$ всех отображений $f:\tilde{X}\to Y$. Действительно, положим для любой пары $(g,h)$ элементов $g\in G$ и $h\in H$ и любой функции $f$ 
\begin{equation}
\label{action_step_group}
((g,h)\otimes f)\,(x)=h *(f(g^{-1}\circ x))\qquad \forall \,x\in \tilde{X}.
\end{equation}
Несложно убедиться, что определенный таким образом оператор $\otimes$ удовлетворяет как свойству тождественности, так и свойству ассоциативности. Следовательно, этот оператор задает действие декартового произведения $G\times H$ групп $G$ и $H$ на множестве $Y^{\tilde{X}}$. По традиции, декартово произведение групп $G$ и $H$ в этой науке называется степенной группой, а действие $\otimes: (Y^{\tilde{X}}\times(G\times H))\to Y^{\tilde{X}}$ --- действием степенной группы $G\times H$ на множестве всех отображений $f:\tilde{X}\to Y$. 

\myitem Следующая наша задача --- обобщить лемму Редфилда-Пойа на случай действия $\otimes$ на $Y^{\tilde{X}}$ степенной группы $G\times H$. Рассмотрим, как обычно, гомоморфизмы $\phi:G\to S_n$, $n=|X|$, и $\psi:H\to S_k$, $k=|Y|$, групп $G$ и $H$ в симметрические группы $S_n$ и $S_k$ соответственно. Пусть $\Sigma_G$ и $\Sigma_H$ есть образы этих гомоморфизмов, то есть группы перестановок множеств $\tilde{X}$ и $Y$, а $\sigma$ и $\tau$ есть образы произвольных элементов $g\in G$ и $h\in H$ при гомоморфизмах $\phi$ и $\psi$. Покажем, что количество орбит группы $G\times H$ на множестве $Y^{\tilde{X}}$ отображений $f$ рассчитывается по формуле
\begin{equation}
\label{gen_lemm_Redf_Polya}
\dfrac{1}{|H|}\sum\limits_{\tau\in \Sigma_H} Z_{\Sigma_G}(l_1(\tau),l_2(\tau),\ldots,l_n(\tau)),\qquad \text{где}\quad
l_i(\tau):=\sum\limits_{r\backslash i}r\cdot j_r,
\end{equation}
а $\{j_1,j_2,\ldots,j_k\}$ есть цикловой тип перестановки $\tau\in  \Sigma_H$.

\mysubitem Согласно лемме Бернсайда, количество орбит элементов $f:\tilde{X}\to Y$ множества отображений под действием группы $G\times H$ определяется по формуле
$$
\dfrac{1}{|G|\cdot |H|}\sum\limits_{\substack{g\in G,\\[0.3ex] h \in H}}\psi(g,h),
$$
где $\psi(g,h)$ есть количество отображений $f$, остающихся неподвижными под действием элементов $g$ и $h$:
\begin{equation}
\label{f_stab_g_h}
(g,h)\otimes f=f\qquad \Longleftrightarrow \qquad h *(f(g^{-1}\circ x))=f(x)\quad \forall \,\,x\in \tilde{X}.
\end{equation}
Следовательно, все, что нам нужно для подсчета количества орбит --- это определить при фиксированных $g$ и $h$ количество $\psi(g,h)$ отображений $f$, удовлетворяющих условию (\ref{f_stab_g_h}). 

\mysubitem Предположим, что перестановка $\sigma\in \Sigma_G$, являющаяся образом элемента $g\in G$ при гомоморфизме $\phi:G\to S_n$, раскладывается в произведение $m$ циклов. Напомним, что раньше, когда на множестве $Y$ никакая группа не действовала (или, что тоже самое, в случае, когда на $Y$ действовала тривиальная группа), условию (\ref{f_stab_g_h}) удовлетворяла любая функция $f$, принимающая одинаковые значения на каждом из циклов обратной к $\sigma$ перестановки $\sigma^{-1}$. Так как при этом на любом цикле функция $f$ могла принимать любое из $k$ возможных значений, то количество таких функций оказывалось равным 
$$
\psi(g,id)=k^{i_1}\cdot k^{i_2}\cdot\ldots\cdot k^{i_n}=k^m.
$$ 

В случае действия на $Y$ нетривиальной группы $H$ рассуждения несколько усложняются. Именно, рассмотрим подмножество элементов $x\in \tilde{X}$, входящих в один и тот же цикл $C_x$ перестановки $\sigma$, и зафиксируем некоторый элемент $x_0$ из этого подмножества. Пусть $\sigma(x_0)=x_1$, $f(x_0)=y_0$, и функция $f:\tilde{X}\to Y$ удовлетворяет условию (\ref{f_stab_g_h}). С учетом введенных обозначений равенство (\ref{f_stab_g_h}) можно переписать в следующем виде:
$$
\tau(f(\sigma^{-1}(x_1)))=f(x_1)\qquad \Longleftrightarrow \qquad \tau(f(x_0))=f(\sigma(x_0))\qquad
\Longleftrightarrow \qquad \tau(y_0)=f(\sigma(x_0)).
$$
Предположим теперь, что перестановка $\tau$ переводит элемент $y_0$ в некоторый элемент $y_1$, то есть $\tau(y_0)=y_1$. В этом случае согласно последнему равенству имеем $y_1=f(\sigma(x_0))=f(x_1)$. Рассмотрим теперь образ $\sigma(x_1)=x_2$ элемента $x_1$ под действием перестановки $\sigma$. Рассуждения, аналогичные проведенным выше, показывают, что в случае, когда $f$ удовлетворяет условию (\ref{f_stab_g_h}), имеют место  равенства
$$
\tau(y_1)=f(\sigma(x_1)) \qquad \Longleftrightarrow \qquad \tau^2(y_0)=f(\sigma^2(x_0)).
$$
Продолжая этот процесс далее, мы через $i$ шагов, где $i$ --- длина цикла $C_x$ в перестановке $\sigma$, получим равенство 
$$
f(\sigma^i(x_0))=\tau^i(y_0). 
$$ 
Но так как $i$ --- длина цикла, то $\sigma^i(x_0)=x_0$, а $f(\sigma^i(x_0))=f(x_0)=y_0$. Следовательно,
\begin{equation}
\label{cond_tau_i_y}
\tau^i(y_0)=y_0,
\end{equation}
то есть в случае, когда $f$ удовлетворяет (\ref{f_stab_g_h}), цикл $C_y$ перестановки $\tau$, содержащий точку $y_0$, должен иметь либо ту же длину, что и цикл $C_x$ перестановки $\sigma$, либо должен иметь длину $r$, являющуюся делителем числа $i$. 

\mysubitem Проведенные выше рассуждения показывают, что задание для некоторого $x_0\in \tilde{X}$ значения $f(x_0)=y_0$ однозначно определяет и значения функции $f$ на всех оставшихся элементах $x_i$ цикла $C_x$. При этом в случае, когда длина $r$ цикла $C_y$ делит $i$, построенная функция (а точнее, ее ограничение на подмножество элементов, входящих в цикл $C_x$) удовлетворяет условию (\ref{f_stab_g_h}) для всех точек $x$, принадлежащих циклу $C_x$. Иными словами, при фиксированных циклах $C_x$ и $C_y$ имеется ровно $r$ функций $f$ (отличающихся своими значениями в точке $x_0$), которые удовлетворяют условию (\ref{f_stab_g_h}) для всех точек $x$, принадлежащих циклу $C_x$. 

Перебирая при фиксированном цикле $C_x$ все циклы $C_y$ заданной перестановки $\tau$, длины $r$ которых делят $i$, и складывая количество элементов во всех этих циклах, мы получаем число $l_i(\tau)$ отображений $f$, удовлетворяющих условию (\ref{f_stab_g_h}) для всех $x$ из заданного цикла $C_x$ перестановки $\sigma$. Это число $l_i(\tau)$ можно определить, таким образом, как количество всех таких $y_0\in Y$, для которых при фиксированном $\tau$ выполнено условие (\ref{cond_tau_i_y}):
$$
\l_i(\tau)=|\{y_0\in Y:\,\tau^i(y_0)=y_0\}|.
$$
Особенно просто подсчитать $l_i(\tau)$ в случае, когда нам известен цикловой тип $\{j_1,j_2,\ldots,j_k\}$ перестановки $\tau\in  \Sigma_H$ --- в этом случае $l_i(\tau)$ рассчитывается, очевидно, по формуле
$$
l_i(\tau):=\sum\limits_{r\backslash i}j_r\cdot r.
$$

\mysubitem Заметим теперь, что подобные операции мы можем проделать для каждого цикла $C_x$ заданной перестановки $\sigma$, и сделать это независимо от способа выбора значений функции $f$ на других элементах цикла. Следовательно, при фиксированных $\sigma$ и $\tau$ искомое нами число $\psi(g,h)$ рассчитывается по формуле
$$
\psi(g,h)=\prod\limits_{i=1}^n l_i(\tau)=[l_1(\tau)]^{i_1}\cdot [l_2(\tau)]^{i_2}\cdot \ldots\cdot [l_n(\tau)]^{i_n},
$$ 
где $\{i_1,i_2,\ldots,i_n\}$ есть цикловой тип перестановки $\sigma$. 

Вспоминая, наконец, что вся информация о цикловом типе перестановок $\sigma\in\Sigma_G$ содержится в цикловом индексе группы $\Sigma_G$, мы и получаем окончательно, что 
$$
\dfrac{1}{|G|\cdot |H|}\sum\limits_{\substack{g\in G,\\[0.3ex] h \in H}}\psi(g,h)=\dfrac{1}{|H|}
\sum\limits_{\tau\in \Sigma_H}Z_{\Sigma_G}(l_1(\tau),l_2(\tau),\ldots,l_n(\tau)).
$$

\mysubitem В заключение еще раз сравним случай действия на $Y^{\tilde X}$ группы $G$ с более общим случаем действия на множестве отображений степенной группы $G\times H$. В первом случае значения функции $f$ на любом цикле $C_x$ перестановки $\sigma$ должны оставаться одинаковыми. При этом они могут принимать любые из $k$ значений, где $k$ --- мощность множества $Y$. Во втором случае значения функции $f$ на элементах цикла $C_x$ могут меняться под действием перестановки $\tau\in \Sigma_H$. Количество же $l_i(\tau)$ допустимых значений $y_0\in Y$ функции $f$ на элементах $x$ цикла $C_x$ определяется из условия (\ref{cond_tau_i_y}) и зависит от циклового типа перестановки $\tau$.  


\myitem Перейдем теперь к обобщению теоремы Пойа на случай действия на $Y^{\tilde X}$ степенной группы $G\times H$. 
Для этого построим с помощью отображения $w:Y\to K$ энумератор $\phi(Y)$ множества $Y$. Будем считать, как обычно, что вес $W(f)$ любого отображения $f:\tilde{X}\to Y$ рассчитывается по формуле (\ref{enum_set_of_maps}).

\begin{theor} Пусть  энумератор $\phi(Y)$ множества $Y$ так задает веса $w(y)$ элементов $y\in Y$, что любые элементы, принадлежащие одному и тому же циклу произвольной перестановки $\tau\in \Sigma_H$, имеют один и тот же вес. Тогда энумератор $\Phi(Y^{\tilde{X}}/G\times H)$ множества орбит элементов $Y^{\tilde{X}}$ под действием группы $G\times H$ рассчитывается по формуле
\begin{equation}
\label{theor_de_Brein}
\Phi(Y^{\tilde{X}}/G\times H)=\dfrac{1}{|H|}\sum\limits_{\tau\in \Sigma_H}
Z_{\Sigma_G}\biggl(L_1(\tau),L_2(\tau),\ldots,L_n(\tau)\biggr),
\end{equation}
где $Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)$ --- цикловой индекс группы $\Sigma_G$ перестановок множества $\tilde{X}$, $L_i(\tau)=\sum[w(y)]^i$, а суммирование в выражении для $L_i(\tau)$ проводится по всем $y$, таким, что $\tau^i(y)=y$.  
\end{theor}

\mysubitem Доказательство данной теоремы практически повторяет доказательство классической теоремы Пойа. В частности, несложно убедиться, что энумератор $\Phi(Y^{\tilde{X}}/G\times H)$ множества орбит элементов $Y^{\tilde{X}}$ под действием группы $G\times H$ равен
$$
\Phi(Y^{\tilde{X}}/G)=\dfrac{1}{|G|\cdot |H|} \sum\limits_{f:(g,f)\otimes f=f}W(f).
$$
Иными словами, задача построения энумератора вновь сводится к определению для каждой пары $(g,f)\in G\times H$ весов $W(f)$ функций $f$, остающихся неподвижными под действием этой пары. 

\mysubitem Рассмотрим произвольный цикл $C_x$ перестановки $\sigma$, являющейся образом элемента $g$ при гомоморфизме $\phi:G\to S_n$ группы $G$ в симметрическую группу $S_n$. Пусть длина этого цикла равна $i$. Как было показано при доказательстве формулы (\ref{gen_lemm_Redf_Polya}), количество отображений $f$, остающихся неподвижными под действием пары $(g,h)$ на любых элементах $x$ цикла $C_x$, совпадает с количеством всех $y\in Y$, для которых выполняется условие $\tau^i(y)=y$. При этом сами значения $y$ функции $f$ могут уже меняться: если $x_0$ --- это одна из точек цикла $C_x$, а $y_0$ --- одно из значений, которые может принимать функция $f$ на $x_0$ (то есть такое $y_0$, что $\tau^i(y_0)=y_0$), то для всех остальных точек $x$ цикла выполняются соотношения
$$
x=\sigma^p(x_0),\qquad f(x)=f(\sigma^p(x_0))=\tau^p(y_0)=y, \qquad p=1,\ldots,i.
$$
Однако мы потребовали в теореме, чтобы все элементы $y$, входящие в один и тот же цикл перестановки, имели бы одинаковый вес, то есть
$$
w(y)=w(y_0) \qquad \forall \,y:\,\,y=\tau^p(y_0).
$$
Следовательно, для всех элементов $x\in\tilde{X}$, входящих в рассматриваемый цикл $C_x$ длины $i$, вес образов этих элементов при отображении $f:\tilde{X}\to Y$ также должен быть одинаков и равен $w(y_0)$. При этом вклад от всех элементов цикла $C_x$ в вес $W(f)$ функции $f$ будет равен $[w(y_0)]^i$. 

\mysubitem Заметим теперь, что в роли $y_0$ может выступать произвольное значение $y$, для которого выполняется условие $\tau^i(y)=y$. Поэтому при подсчете всех функций, остающихся неподвижными под действием пары $(g,h)$, у нас должен появиться сомножитель вида
$$
L_i(\tau)=\sum\limits_{y:\,\tau^i(y)=y}[w(y)]^i.
$$
Дальнейшие рассуждения дословно повторяют рассуждения, проведенные при доказательстве теоремы Пойа. Следовательно, в рассматриваемом случае действия группы $G\times H$ мы для количества орбит имеем энумератор вида
$$
\Phi(Y^{\tilde{X}}/G\times H)=\dfrac{1}{|H|}\sum\limits_{\tau\in \Sigma_H}
Z_{\Sigma_G}\biggl(\,\sum\limits_{y: \,\tau^i(y)=y}w(y),\sum\limits_{y: \,\tau^i(y)=y}w^2(y),\ldots,
\sum\limits_{y: \,\tau^i(y)=y}w^n(y)\biggr),
$$
где $Z_{\Sigma_G}(x_1,x_2,\ldots,x_n)$ --- цикловой индекс группы $\Sigma_G$ перестановок множества $\tilde{X}$.

\mysubitem В заключение еще раз обратим внимание на фигурирующее в формулировке теоремы условие, связанное с энумератором $\phi(Y)$ множества $Y$. Именно, нам необходимо, чтобы все элементы множества $Y$, принадлежащие одной и той же орбите, имели одинаковые веса. Вообще говоря, это --- довольно ограничительное условие, и зачастую не очень понятно, как в конкретной задаче добиться его выполнения. 

Однако существует важный частный случай, когда это условие всегда можно выполнить: если группа $H$ представима в виде декартова произведения некоторых подгрупп, то можно для элементов, на которых действует данная подгруппа,  назначить свой (одинаковый для всех этих элементов) вес. 

Например, в задаче о раскладке шаров по пяти ящикам, два из которых --- круглые, а три --- квадратные, группа $H$ представляется в виде декартова произведения $S_2\times S_3$. Поэтому элементам, на которых действует подгруппа $S_2$, можно назначить один вес (например, $w(y)=r$), а элементам, на которых действует подгруппа $S_3$ --- другой (например, $w(y)=s$). 



\section*{Упражнения}

\begin{exerc} Пусть у нас имеется браслет из четырех бусинок, каждая из которых окрашена в один из двух цветов. Мы по-прежнему не различаем два браслета, получаемые один из другого вращениями вокруг оси, проходящей через центр симметрии этого браслета. Предположим, однако, что мы теперь считаем неразличимыми и любые два браслета, получающиеся один из другого заменой цвета бусинки на противоположный. Иными словами, мы можем различать два цвета, но не можем точно сказать, какой из них какой. Сколько в этом случае существует неэквивалентных друг другу браслетов? 

\end{exerc}

\begin{exerc} Подсчитать количество способов распределить три белых и три черных шара по одному красному и двум синим ящикам. 
\end{exerc}

\begin{exerc} Пусть для задачи из предыдущего упражнения энумератор $\phi(Y)$ множества цветов построен следующим образом: для элементов $y$, на которых действует подгруппа $S_1$, вес $w(y)=r$, а для элементов, на которых действует подгруппа $S_2$, вес $w(y)=b$. Построить для этой задачи энумератор $\Phi(r,b)$ множества орбит.   
\end{exerc}


\section*{Решение упражнений}

\begin{sol_exerc} В данном случае на множестве $\tilde{X}=\{x_1,\ldots,x_4\}$ бусинок действует группа $G=D_4$, а на множестве $Y=\{y_1,y_2\}$ цветов действует группа $S_2$. Цикловой индекс группы $\Sigma_{D_4}$ перестановок элементов множества $\tilde{X}$ равен
$$
Z_{\Sigma_{D_4}}(a_1,a_2,a_3,a_4)=\dfrac{1}{8}[a_1^4+2a_1^2a_2+3a_2^2+2a_4].
$$ 
В группе $\Sigma_{S_2}\equiv S_2$ имеются две перестановки --- тождественная перестановка $id$ и перестановка $\tau$, меняющая местами два элемента множества $Y$. Для тождественной перестановки все числа $l_i(id)$ в формуле (\ref{gen_lemm_Redf_Polya}) равны двум, а для перестановки $\tau$ имеем
$$
l_1(\tau)=l_3(\tau)=0,\qquad l_2(\tau)=l_4(\tau)=2. 
$$
Поэтому, согласно (\ref{gen_lemm_Redf_Polya}), количество искомых браслетов равно
$$
\dfrac{1}{16}[(2^4+2\cdot 2^3+3\cdot 2^2+2\cdot 2)+(3\cdot 2^2+2\cdot 2)]=4.
$$

\end{sol_exerc}


\begin{sol_exerc} С формальной точки зрения окраска шести шаров в два различных цвета означает, что на множестве 
$$
\tilde{X}=\{x_1,\ldots,x_6\}
$$
шаров действует группа $G=S_3\times S_3$, равная декартовому произведению пары симметрических групп $S_3$. Аналогично, на множестве
$$
Y=\{y_1,y_2,y_3\}
$$
ящиков действует группа $H=S_1\times S_2$. 

Несложно доказать, что цикловой индекс декартового произведения пары групп равен произведению цикловых индексов каждой из этих групп. Так как
$$
Z_{S_3}=\dfrac{1}{6}[a_1^3+3a_1a_2+2a_3], 
$$
то
$$
Z_G=\dfrac{1}{36}[a_1^3+3a_1a_2+2a_3]^2=\dfrac{1}{36}[a_1^6+6 a_1^4 a_2+4 a_1^3 a_3+9 a_1^2 a_2^2+12 a_1 a_2 a_3+4 a_3^2].
$$

В образе $\Sigma_H$ группы $H$ имеется всего два вида перестановок --- тождественная перестановка $id$ и три перестановки, меняющие местами пару элементов множества $Y$. В случае тождественной перестановки все $l_i=3=|Y|$, $i=1,2,3$. В случае перестановки $\tau$ циклового типа $\{j_1,j_2\}=\{1,1\}$ имеем
$$
l_1(\tau)=1\cdot j_1=1,\qquad l_2(\tau)=1\cdot j_1+2\cdot j_2=1+2=3,\qquad l_3(\tau)=1\cdot j_1=1.
$$

Подставляя вычисленные выше значения $l_i(\tau)$ в формулу (\ref{gen_lemm_Redf_Polya}), получаем, что для рассматриваемой задачи количество способов раскладки равно
$$
\dfrac{1}{2}\Bigl(\dfrac{1}{36}[3^3+3 \cdot 3^2+2\cdot 3]^2+
\dfrac{1}{36}[1+3 \cdot 3+2]^2\Bigr)=\dfrac{1}{2}(100+4)=52.
$$

\end{sol_exerc}


\begin{sol_exerc} Итак, предположим, что энумератор $\phi(r,b)$ для множества $Y$ задан с помощью соотношений вида
$$
w(y_1)=r,\qquad w(y_2)=w(y_3)=b.
$$
В этом случае вес $W(f)$ любой функции $f:\tilde{X}\to Y$, описывающий некоторую раскладку шести различимых шаров по трем различимым ящикам, имеет вид
$$
W(f)=\alpha_f\cdot r^t\cdot b^{6-t}.
$$

Теперь предположим, что на множестве $Y^{\tilde{X}}$ всех отображений действует степенная группа $G\times H$, где $G=S_3\times S_3$, а $H=S_1\times S_2$. Наша задача --- подсчитать веса функций, значения которых разрешены для каждой конкретной перестановки $\tau\in\Sigma_H$.

Начнем с тождественной перестановки $\tau=id$. Для этой перестановки все элементы $y\in Y$ удовлетворяют условию (\ref{cond_tau_i_y}) для любого цикла $C_x$ длины $i$ перестановки $\sigma\in\Sigma_G$. Следовательно,
$$
L_i(id)=r^i+2b^i.
$$

Теперь рассмотрим перестановку $\tau$, меняющую местами элементы $y_2$ и $y_3$. Для этой перестановки в случае $i=1$ и $i=3$ только $y_1$ удовлетворяет условию (\ref{cond_tau_i_y}), поэтому
$$
L_1(\tau)=r,\qquad L_3(\tau)=r^3.
$$
В случае $i=2$ все три элемента множества $Y$ удовлетворяют условию (\ref{cond_tau_i_y}), поэтому для такого значения параметра $i$ имеем
$$
L_2(\tau)=r^2+2b^2.
$$

Подставляя указанные значения $L_i(\tau)$ в формулу (\ref{theor_de_Brein}), получаем энумератор $\Phi(r,b)$ множества орбит вида
$$
\Phi(r,b)=\dfrac{1}{72}\bigl([(r+2b)^3+3(r+2b)(r^2+2b^2)+2(r^3+2b^3)]^2+[r^3+3r(r^2+2b^2)+2r^3]^2\bigr)=
$$
$$
=r^6+2 r^5 b+6 r^4 b^2+10 r^3 b^3+13 r^2 b^4+12 r b^5+8 b^6.
$$
Коэффициенты при $r^tb^{6-t}$ дают нам количество различных способов раскладки трех белых и трех черных шаров по одному красному и двум синим ящикам так, чтобы $t$ шаров находились в красном, а $(6-t)$ --- в двух синих ящиках.

\end{sol_exerc}



\section{Композиционная формула для обыкновенных производящих функций}


\section{Перечисление непомеченных графов и деревьев}


\myitem Предложенный Пойа подход к формализации понятия окраски элементов $x\in\tilde{X}$ геометрической фигуры $\Gamma$ цветами из множества $Y$ позволяет применять теорию перечисления Пойа для решения значительно более широкого класса задач. 

Действительно, пусть $Y$ есть некоторое произвольное множество (не обязательно множество цветов), для которого с помощью отображения $w:Y\to K$ построен некоторый энумератор (или, в частном случае $K=\C[[z]]$, производящая функция) $\phi(Y)$. Пусть, далее, $\tilde{X}$ есть некоторое множество помеченных объектов, на котором действует группа $G$. Предположим, наконец, что любой перечисляемый нами объект, помеченный элементами множества $\tilde{X}$, можно рассматривать как результат некоторого отображения $f:\tilde{X}\to Y$ множества $X$ в множество $Y$. Тогда для перечисления непомеченных объектов такого рода можно использовать теорему Пойа. 

\myitem В качестве иллюстрации этого утверждения рассмотрим задачу перечисления непомеченных связных графов. Пусть $Y$ есть множество всех таких графов, и пусть $c(z)$ есть обыкновенная производящая функция
$$
c(z)=c_1z+c_2z^2+\ldots+c_kz^k+\ldots,
$$
коэффициенты $c_k$ которой описывают количество связных графов, построенных на $k$ непомеченных вершинах. Наша задача --- определить эти числа $c_k$.

\mysubitem Рассмотрим для этого произвольный (не обязательно связный) граф $G$, построенный на $n$ непомеченных вершинах. Предположим, что он состоит из $m$ односвязных компонент. Введем множество $\tilde{X}=\{1,2,\ldots,m\}$. Тогда любое  отображение $f:\tilde{X}\to Y$ описывает нам некоторый граф $\hat{G}$, каждая компонента связности которого помечена некоторым числом $i\in\tilde{X}.$ При этом исходный граф $G$ можно рассматривать как орбиту элементов $f$ множества $Y^{\tilde X}$ таких отображений под действием группы $S_m$ перестановок всех $m$ компонент связности графа $\hat{G}$. Как следствие, согласно теореме Пойа, производящая функция $g_m(z)$ для количества всех непомеченных графов $G$, имеющих ровно $m$ компонент связности, рассчитывается по формуле
$$
g_m(z)=Z_{S_m}\biggl(\sum\limits_{k=0}^{+\infty}c_kz^k,\sum\limits_{k=0}^{+\infty}c_kz^{2k},\ldots,
\sum\limits_{k=0}^{+\infty}c_kz^{mk}\biggr)=Z_{S_m}(c(z),c(z^2),\ldots,c(z^m)).
$$

\mysubitem Введем теперь обыкновенную производящую функцию
$$
g(z)=g_1z^1+g_2z^2+\ldots+g_nz^n+\ldots,
$$
коэффициенты $g_n$ которой описывают количество \emph{всех} графов, построенных на $n$ непомеченных вершинах. В предыдущем параграфе мы объяснили, как с помощью теории Рэдфилда-Пойа подсчитать числа $g_n$. Будем считать, что они нам известны. 

Заметим, что эту же производящую функцию $g(z)$ можно получить, суммируя производящие функции $g_m(z)$ по всем возможным компонентам связности графа:
$$
g(z)=\sum\limits_{n=1}^{+\infty}g_nz^n=\sum\limits_{m=1}^{+\infty}g_m(z)=\sum\limits_{m=1}^{+\infty}Z_{S_m}(c(z),c(z^2),\ldots,c(z^m)).
$$ 


\mysubitem Напомним, что цикловой индекс $Z_{S_m}(a_1,\ldots,a_m)$ может быть получен как коэффициент при $t^n$ в разложении производящей функции 
$$
S(t)=\exp\Bigl( a_1\dfrac{t^1}{1}+a_2\dfrac{t^2}{2}+\ldots+a_n\dfrac{t^n}{n}+\ldots\Bigr)
$$
по степеням формальной переменной $t$:
$$
S(t)=1+\sum\limits_{m=1}^{+\infty}Z_{S_m}(a_1,\ldots,a_m)\cdot t^m.
$$
Как следствие,
$$
S(1)=1+\sum\limits_{m=1}^{+\infty}Z_{S_m}(a_1,\ldots,a_m)=\exp\Bigl( a_1+\dfrac{a_2}{2}+\ldots+\dfrac{a_n}{n}+\ldots\Bigr),
$$
а 
\begin{equation}
\label{sum_cicl_ind_cz}
1+\sum\limits_{m=1}^{+\infty}Z_{S_m}(c(z),c(z^2),\ldots,c(z^m))=\exp\Bigl( c(z)+\dfrac{c(z^2)}{2}+\ldots+\dfrac{c(z^n)}{n}+\ldots\Bigr).
\end{equation}

\mysubitem С учетом формулы (\ref{sum_cicl_ind_cz}) мы получаем в результате следующее соотношение, связывающее производящие функции $g(z)$ и $c(z)$, описывающие количество всех непомеченных графов и всех непомеченных связных графов:
$$
1+g(z)=\exp\Bigl( c(z)+\dfrac{c(z^2)}{2}+\ldots+\dfrac{c(z^n)}{n}+\ldots\Bigr).
$$ 
Используя это равенство, можно получить формулу вида 
\begin{equation}
\label{number_con_graphs}
c_n=\sum\limits_{d \backslash n}\dfrac{\mu(d)}{d}g_{n/d},
\end{equation}
выражающую количество $c_n$ связных графов, построенных на $n$ непомеченных вершинах, через известные значения $g_n$ (смотри Упражнение ...).

\myitem Аналогичный подход можно использовать и для перечисления всех непомеченных корневых деревьев. 

\mysubitem Действительно, рассмотрим произвольное корневое непомеченное дерево, построенное на $(n+1)$-й вершине, корень которого имеет степень $m$ (так называемое корневое дерево степени $m$). Понятно, что любое такое дерево эквивалентно набору, состоящему из $m$ корневых непомеченных деревьев, построенных на $n$ вершинах. 

Введем теперь множество $\tilde{X}=\{1,\ldots,m\}$ и рассмотрим отображение этого множества в множество $Y$ всех корневых непомеченных деревьев. Тогда любое отображение $f:\tilde{X}\to Y$ описывает нам некоторую структуру, состоящую из $m$ корневых деревьев, каждая корневая вершина которой помечена одним из чисел множества $\tilde{X}$. Действие симметрической группы $S_m$ на множестве $Y^{\tilde{X}}$ всех таких отображений $f$ разбивает это множество на классы эквивалентности, каждый из которых можно трактовать как набор, состоящий из $m$ корневых непомеченных деревьев на $n$ вершинах, то есть как корневое дерево степени $m$, построенное на $(n+1)$-й вершине. Согласно теореме Пойа, количество таких деревьев описывается производящей функцией вида
$$
a_m(z)=Z_{S_m}(a(z),a(z^2),\ldots,a(z^m)),\qquad\qquad  a_0(z):=1,
$$
где $a(z)$ есть производящая функция, описывающая все множество корневых непомеченных деревьев. 

\mysubitem По построению, коэффициент при $z^n$ у функции $a_m(z)$ описывает количество корневых деревьев степени $m$, построенных на $(n+1)$-й вершине. Удобнее вместо $a_m(z)$ рассматривать функцию 
$$
\hat{a}_m(z)=z\cdot a_m(z),
$$
коэффициент при $z^{n+1}$ в которой даст количество корневых деревьев степени $m$, построенных на $(n+1)$-й вершине. 

\mysubitem Просуммируем функции $\hat{a}_m(z)$ по всем индексам $m=0,1,2,\ldots$. В результате мы получим производящую функцию
$$
a(z)=a_1z+a_2z^2+\ldots+a_nz^n+\ldots,
$$
коэффициент $a_n$ в которой равен количеству корневых непомеченных деревьев произвольной степени, построенных на $n$ вершинах:
$$
a(z)=\sum\limits_{m=0}^{+\infty}\hat{a}_m(z)=z\sum\limits_{m=0}^{+\infty}a_m(z)=z+z\sum\limits_{m=1}^{+\infty}
Z_{S_m}(a(z),a(z^2),\ldots,a(z^m)).
$$
Из последнего равенства с учетом (\ref{sum_cicl_ind_cz}) получается следующее уравнение на производящую функцию $a(z)$:
\begin{equation}
\label{unlabelled_rooted_trees}
a(z)=z\exp\Bigl(a(z)+\dfrac{a(z^2)}{2}+\ldots+\dfrac{a(z^n)}{n}+\ldots\Bigr).
\end{equation}

В упражнении ... предлагается с помощью этого уравнения получить следующее рекуррентное соотношение, выражающее количество $a_{n+1}$ корневых деревьев на $(n+1)$-й вершине через числа $a_1,\ldots,a_n:$
\begin{equation}
\label{number_rooted_trees}
a_{n+1}=\dfrac{1}{n}\sum\limits_{i=1}^{n}a_{n+1-i}\sum\limits_{d \backslash i}d\cdot a_d.
\end{equation}
Все различные непомеченные корневые деревья для малых $n$ показаны на рис.?.

\myitem Интересно отметить, что первым количество всех непомеченных корневых деревьев подсчитал Артур Кэли еще в 1857 году \cite{Cayley_unlabelled_trees}. И сделал он это с помощью довольно элементарных рассуждений, очень похожих на те, которые провел Эйлер при выводе производящей функции для количества $p(n)$ всех разбиений натурального числа $n$. 

\mysubitem Напомним, что идея вывода формулы
$$
\sum\limits_{n\geq 0} p(n)z^n=\prod\limits_{i\geq 1} \dfrac{1}{1-z^i}=(1+z+z^2+z^3+\ldots)\cdot (1+z^2+z^4+\ldots)\cdot (1+z^3+z^6+\ldots)\cdot \ldots
$$
для количества $p(n)$ всех разбиений числа $n$ состояла в переформулировке этой задачи на языке раскладки неразличимых предметов по $n$ различимым ящикам. Именно, мы складывали в первый ящик единицы, во второй --- двойки, в третий --- тройки и так далее. 

\mysubitem Вернемся к задаче перечисления корневых непомеченных деревьев. После удаления корня $A$ любое такое дерево, построенное на $(n+1)$-й вершине, распадается на некоторое количество поддеревьев, корнями которых являются смежные с $A$ вершины. На языке раскладки предметов по ящикам это действие можно интерпретировать так: поместим в нулевой ящик корень дерева, в первый ящик положим корневые поддеревья, построенные на одной вершине, во второй ящик поместим корневые поддеревья, построенные на двух вершинах, и так далее. Однако, в отличие от разбиения натурального числа, здесь в каждом ящике содержатся деревья разного вида. Так, в третьем ящике окажутся как корневые деревья вида $--$, так и корневые деревья вида $<$. Чтобы учесть эти различия, разобьем каждый $i$-й ящик на $a_i$ подящиков, где $a_i$ --- количество корневых деревьев, построенных на $i$ вершинах, и будем в каждый такой подящик складывать только лишь поддеревья данного вида. В результате любой такой раскладке поддеревьев по $m$ подящикам будет отвечать некоторое непомеченное дерево, корень которого имеет степень $m$. Как следствие, количество всех непомеченных корневых деревьев описывается обыкновенной производящей функцией, удовлетворяющей уравнению
\begin{equation}
\label{formula_Cayley}
a(z)=\sum\limits_{n>0}a_nz^n=z\prod\limits_{i\geq 1}\biggl(\dfrac{1}{1-z^i}\biggr)^{a_i}.
\end{equation}

\mysubitem Для того, чтобы доказать эквивалентность формул (\ref{unlabelled_rooted_trees}) и (\ref{formula_Cayley}), заметим, что 
$$
y(z)=\exp(\log(y(z))\quad \Longrightarrow \quad a(z)=
z\cdot\exp\biggl(\log\biggl(\prod\limits_{i\geq 1}\biggl(\dfrac{1}{1-z^i}\biggr)^{a_i}\biggr)\biggr)
=z\cdot\exp\biggl(\sum\limits_{i\geq 1}a_i\cdot\log\dfrac{1}{1-z^i}\biggr).
$$
Учитывая, что
$$
\log\dfrac{1}{1-z^i}=\sum\limits_{k\geq 1}\dfrac{z^{k\cdot i}}{k},
$$
получаем из (\ref{formula_Cayley}) равенство вида
$$
a(z)=z\cdot\exp\biggl(\sum\limits_{i\geq 1}a_i\sum\limits_{k\geq 1}\dfrac{z^{k\cdot i}}{k}\biggr)=
z\cdot\exp\biggl(\sum\limits_{i,k\geq 1}\dfrac{a_iz^{k\cdot i}}{k}\biggr)=
z\cdot\exp\biggl(\sum\limits_{k\geq 1}\dfrac{T(z^k)}{k}\biggr),
$$
то есть формулу (\ref{unlabelled_rooted_trees}).

\myitem Заметим, что при перечислении непомеченных дискретных объектов довольно часто возникают производящие функции кратных аргументов (например, производящие функции вида $f(z^2)$, $f(z^5)$ и так далее). Довольно часто появление таких функций можно объяснить с помощью простейших комбинаторных рассуждений. В качестве характерного примера таких рассуждений рассмотрим задачу перечисления всех корневых непомеченных деревьев, любая вершина которого имеет степень, меньшую или равную двум.

\mysubitem Перечислим вначале все помеченные корневые деревья подобного типа. Несложно понять, что производящая функция $B(z)$ для количества таких деревьев описывается следующим рекурсивным функциональным уравнением:
$$
B(z)=1+z\cdot B^2(z)/2.
$$
Действительно, любое нетривиальное дерево такого типа можно представить в виде корня и двух \emph{неупорядоченных} поддеревьев того же самого вида. Если бы мы различали, какое из этих поддеревьев является правым, а какое --- левым (то есть если бы мы рассматривали \emph{плоские} деревья рассматриваемого типа), то мы бы получили в правой части выражение вида $z\cdot B^2(z)$. Так как у нас деревья не плоские, то порядок этих деревьев значения не имеет, и нам следует это выражение поделить на два.

\mysubitem Теперь перейдем к задаче перечисления непомеченных корневых деревьев. Разобьем все множество нетривиальных деревьев такого типа на два блока. К первому из них отнесем деревья, у которых корень имеет степень два, а два его поддерева идентичны друг другу (так называемые симметричные деревья). Во второй блок включим все остальные  (несимметричные) деревья. Очевидно, что 
\begin{equation}
\label{b_b1_b2}
b(z)=1+\sum\limits_{n=1}^{+\infty}b_nz^n=1+b^{(1)}(z)+b^{(2)}(z),
\end{equation}
где $b^{(1)}(z)$ и $b^{(2)}(z)$ --- производящие функции, описывающие деревья из первого и второго блоков соответственно. 

\mysubitem Построим вначале производящую функцию $b^{(1)}(z)$, описывающую количество симметричных деревьев. Прежде всего заметим, что любое такое дерево может быть построено только на нечетном числе вершин, поэтому коэффициенты при четных степенях $z$ у этой функции равны нулю. Далее, после удаления корня любое такое дерево распадается на два идентичных поддерева, каждое из которых может быть произвольным (не обязательно симметричным) деревом рассматриваемого в задаче вида. Иными словами, любому симметричному дереву на $(2n+1)$-й вершине отвечает некоторое произвольное дерево, построенное на $n$ вершинах. Как следствие, количество $b_{2n+1}^{(1)}$ симметричных деревьев на $(2n+1)$ вершинах совпадает с количеством $b_n$ всех деревьев на $n$ вершинах, а производящая функция
$$
b^{(1)}(z)=\sum\limits_{n=0}^{+\infty}b_{2n+1}^{(1)}z^{2n+1}=\sum\limits_{n=0}^{+\infty}b_nz^{2n+1}=z\cdot b(z^2).
$$

\mysubitem Нам осталось найти функцию $b^{(2)}(z)$, описывающую количество несимметричных деревьев. Для этого докажем, что в случае непомеченных корневых деревьев справедливо равенство
\begin{equation}
\label{equiv_sym_nonsym}
z\cdot b^2(z)=b^{(1)}(z)+2b^{(2)}(z).
\end{equation}
Действительно, мы уже говорили выше, что выражение вида $z\cdot b^2(z)$ описывает, по сути, количество нетривиальных \emph{плоских} корневых деревьев рассматриваемого вида. Для доказательства равенства (\ref{equiv_sym_nonsym}) осталось заметить, что любое несимметричное пространственное корневое дерево можно уложить на плоскости двумя способами (слагаемое $2b^{(2)}(z)$), а симметричное пространственное дерево --- одним (слагаемое $b^{(1)}(z)$). 

Выражая теперь из (\ref{equiv_sym_nonsym}) производящую функцию $b^{(2)}(z)$ и подставляя результат в формулу (\ref{b_b1_b2}), мы получаем на $b(z)$ следующее функциональное уравнение:
$$
b(z)=1+\dfrac{1}{2}z\cdot b^2(z)-\dfrac{1}{2}b^{(1)}(z)+b^{(1)}(z)=
1+\dfrac{1}{2}z\cdot b^2(z)+\dfrac{1}{2}b^{(1)}(z)=1+\dfrac{z}{2}(b^2(z)+b(z^2)).
$$
Соответствующая этой функции числовая последовательность, описывающая количество корневых деревьев рассматриваемого типа, начинается с чисел $1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207$ (последовательность $A001190$ в OEIS). 


\section*{Упражения}
\begin{exerc} Доказать, что количество $c_n$ непомеченных связных графов на $n$ вершинах может быть выражено через количество $g_n$ всех непомеченных графов по формуле
$$
c_n=\sum\limits_{d \backslash n}\dfrac{\mu(d)}{d}g_{n/d}.
$$
\end{exerc}

\begin{exerc} Доказать, что количество корневых непомеченных деревьев на $(n+1)$-й вершине может быть вычислено с помощью рекуррентного соотношения
$$
a_{n+1}=\dfrac{1}{n}\sum\limits_{i=1}^{n}a_{n+1-i}\sum\limits_{d \backslash i}d\cdot a_d; \qquad a_1 = 1.
$$

\end{exerc}

\begin{exerc} Рассмотрим множество $M$ корневых деревьев, у которых каждая вершина имеет трёх (возможно, пустых) упорядоченных потомков. Введём производящую функцию $f(z)$ для таких деревьев. Легко видеть, что эта функция удовлетворяет уравнению 
$$
f(z)=1+z\cdot f^3(z).
$$
Выразите производящую функцию $s(z)$, описывающую количество симметричных деревьев  (рис. \ref{fig:symtrees}) из $M$, через производящую функцию $f(z)$. Преобразуйте полученное выражение так, чтобы $s(z)$ выражалась через полином от $z,f(z),f(z^2),f(z^3),\dots$ Найдите явный вид коэффициентов $s(z)$ с помощью формулы обращения Лагранжа.
\end{exerc}

\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/symtrees.eps}
\caption{Симметричное дерево}
\label{fig:symtrees}
\end{figure}


\begin{exerc} 
Полученное в предыдущем упражнении равенство для $s(z)$ докажите с помощью прямых комбинаторных рассуждений.
\end{exerc}

\begin{exerc} 
Найдите уравнение на производящую функцию, описывающую количество корневых треугольных кактусов на $n$ непомеченных вершинах.
\end{exerc}


\section*{Решение упражнений}

\begin{sol_exerc} 

\end{sol_exerc}


\begin{sol_exerc} 
Перепишем уравнение на производящую функцию для корневых деревьев в следующем виде:
$$
\frac{a(z)}{z}=\exp\Bigl(a(z)+\dfrac{a(z^2)}{2}+\ldots+\dfrac{a(z^n)}{n}+\ldots\Bigr).
$$
Взяв производную от левой и правой части, мы получим, что 
$$
\Bigl ( \frac{a(z)}{z} \Bigr )'=\exp\Bigl(a(z)+\dfrac{a(z^2)}{2}+\ldots+\dfrac{a(z^n)}{n}+\ldots\Bigr) \cdot (a'(z)+z\cdot a'(z^2)+\ldots+z^{n-1}\cdot a'(z^n)+\ldots) = 
$$
$$
\frac{a(z)}{z}\cdot (a'(z)+ z\cdot a'(z^2)+\ldots+z^{n-1}\cdot a'(z^n)+\ldots).
$$

Из этого следует, что

$$
\sum_{i=1}^\infty i\cdot a_{i+1} \cdot z^{i-1} =\Bigl (\sum_{i=0}^\infty a_{i+1} \cdot z^i \Bigr ) \cdot \Bigl( \sum_{i=1}^\infty i\cdot a_i \cdot z^{(i-1)} + \sum_{i=0}^\infty i\cdot a_i \cdot z^{2i-1}+ \ldots + \sum_{i=0}^\infty i\cdot a_i \cdot z^{ni-1} + \ldots \Bigr ).
$$

Приравняем коэффициенты в левой и правой частях равенства при $z^{n-1}$:
$$
n\cdot a_{n+1} = \sum_{i=1}^n a_{n+1-i} \cdot  \sum_{d\,\backslash n}d\cdot a_d,
$$
что и требовалось доказать.
\end{sol_exerc}



\begin{sol_exerc} 
Симметричное дерево из множества $M$ является либо пустым, либо состоит из корня, три поддерева которого устроены следующим образом: центральное  поддерево — симметричное дерево из множества $M$ (описывается производящей функцией $s(z)$), а два крайних — произвольные деревья из $M$, зеркальные отражения друг друга. Они описываются функцией $f(z^2)$. Таким образом,
$$
s(z)=1+z\cdot s(z)\cdot f(z^2) \quad \Rightarrow \quad s(z)=\frac{1}{1-z\cdot f(z^2)} = \frac{1 + z\cdot f(z^2)}{1-z^2 \cdot f(z^2)}.
$$

Заметим теперь, что из равенства $f(z)=1+z\cdot f^3(z)$ следует, что $f(z)=\frac{1}{1-z\cdot f^2(z)}$. А значит, равенство для $s(z)$ можно переписать так:
$$
s(z)=f(z^2)+z\cdot f^2(z^2).
$$

\end{sol_exerc}


\begin{sol_exerc} 
Рассмотрим равенство $s(z)=f(z^2)+z\cdot f^2(z^2).$ Ясно, что слагаемое $f(z^2)$ содержит только чётные степени $z$, а слагаемое $z\cdot f^2(z^2)$ — только нечётные. Докажем комбинаторно, что количество симметричных деревьев на чётном числе вершин действительно описывается производящей функцией $f(z^2)$. Для этого возьмём произвольное симметричное дерево на $2n$ вершинах. Выделим в таком дерево корень $v_1$, его центрального сына $v_2$, центрального сына $v_3$ этого сына и так далее, всего $2k$ вершин. Теперь поменяем местами правое поддерево $v_1$ и правое поддерево $v_{2k}$, правое поддерево $v_2$ и правое поддерево $v_{2k-1}$, и так далее. После этого удалим ребро $(v_k, v_{k+1})$ и назначим корнями двух получившихся после этого деревьев вершины $v_k$ и $v_{k+1}$. Результат такого преобразования для дерева, приведённого в условии задачи, показан на рис. \ref{fig:symtrees2}. Описанное преобразование обратимо, и в его результате мы получили пару произвольных одинаковых деревьев, производящая функция для которых — действительно $f(z^2)$. 

В случае, если исходное дерево имело нечётное количество вершин, разобьём его на два дерева: первое, состоящее из корня исходного дерева, его левого и правого потомков ($z\cdot f(z^2)$), и второе, построенное на оставшихся вершинах. Второе дерево имеет чётное число вершин и, следовательно, описывается функцией $f(z^2)$, как было доказано ранее.  

\end{sol_exerc}
\begin{figure}[h]
\centering
  \includegraphics[scale=0.6]{pics/symtrees2.eps}
\caption{Пара одинаковых деревьев}
\label{fig:symtrees2}
\end{figure}


\begin{sol_exerc} 
Рассмотрим произвольный корневой треугольный кактус. Удалив в нём корень, мы получим неупорядоченный набор из заранее не фиксированного числа $m$ пар корневых кактусов; корни в каждой паре соединены ребром. В соответствии с теоремой Редфилда-Пойа, по аналогии с корневыми деревьями, можно заключить, что производящая функция $f(z)$ для корневых кактусов удовлетворяет уравнению
$$
f(z)=z+z\sum\limits_{m=1}^{+\infty}Z_{S_m}(g(z),g(z^2),\ldots,g(z^m)) = z\exp\Bigl(g(z)+\dfrac{g(z^2)}{2}+\ldots+\dfrac{g(z^n)}{n}+\ldots\Bigr).
$$ 
Здесь $g(z)$ — производящая функция для пар корневых кактусов, корни которых соединены ребром. Так как эти пары — неупорядоченные, на их элементах действует группа $S_2$, а значит, 
$$
g(z)=\frac{f^2(z)+f(z^2)}{2}.
$$
Полученная пара равенств как раз и позволяет перечислить все корневые кактусы на $n$ вершинах.
\end{sol_exerc}


\newpage

\bibliography{Ref_book}

\end{document}